SIMULATION OF QUANTUM SEARCH ALGORITHM
0
Citation
7
Reference
10
Related Paper
Abstract:
The rapid progress of computer science has been accompanied by a corresponding evolution of computation, from classical computation to quantum computation. As quantum computing is on its way to becoming an established discipline of computing science, much effort is being put into the development of new quantum algorithms. One of quantum algorithms is Grover's algorithm, which is used for searching an element in an unstructured list of N elements with quadratic speed-up over classical algorithms. In this work, Quantum Computer Language (QCL) is used to make a Grover's quantum search simulation in a classical computer document.Keywords:
Quantum sort
In quantum information processing (QIP), the quantum Fourier transform (QFT) has a plethora of applications [1] [2] [3]: Shor's algorithm and phase estimation are just a few well-known examples. Shor's quantum factorization algorithm, one of the most widely quoted quantum algorithms [4] [5] [6] relies heavily on the QFT and efficiently finds integer prime factors of large numbers on quantum computers [4]. This seminal ground-breaking design for quantum algorithms has triggered a cascade of viable alternatives to previously unsolvable problems on a classical computer that are potentially superior and can run in polynomial time. In this work we examine the QFT's structure and implementation for the creation of a quantum music note detection algorithm both on a simulated and a real quantum computer. Though formal approaches [7] [1] [8] [9] exist for the verification of quantum algorithms, in this study we limit ourselves to a simpler, symbolic representation which we validate using the symbolic SymPy [10] [11] package which symbolically replicates quantum computing processes. The algorithm is then implemented as a quantum circuit, using IBM's qiskit [12] library and finally period detection is exemplified on an actual single musical tone using a varying number of qubits.
Quantum Fourier transform
Quantum sort
Quantum circuit
Cite
Citations (1)
We present a quantum algorithm solving the greatest common divisor (GCD) problem. This quantum algorithm possesses similar computational complexity with classical algorithms, such as the well-known Euclidean algorithm for GCD. This algorithm is an application of the quantum algorithms for the hidden subgroup problems, the same as Shor factoring algorithm. Explicit quantum circuits realized by quantum gates for this quantum algorithm are provided. We also give a computer simulation of this quantum algorithm and present the expected outcomes for the corresponding quantum circuit.
Greatest common divisor
Cite
Citations (2)
Cite
Citations (54)
In 1994, Peter Shor discovered a polynomial time quantum algorithm for factoring and discrete logarithm. Two years later, in 1996, Lov Grover discovered a search algorithm which is quadratically better than conventional search. By now, each of the two algorithms has developed into a line of research which goes well beyond the original algorithm. Shor's algorithm has inspired the study of quantum Fourier sampling which has resulted in more quantum algorithms for number-theoretic and group-theoretic problems. Grover's algorithm has developed into the area of quantum query algorithms.I will survey the developments in quantum query algorithms. The topics will include: applications of Grover's algorithm to element distinctness and other problems, lower bounds on quantum algorithms and the use of quantum random walks to design better search algorithm. I will also describe how some of techniques in this area can be used as "quantum black boxes" in an otherwise classical algorithm.
Quantum sort
Quantum Fourier transform
Quantum walk
Cite
Citations (1)
Quantum Fourier transform
Quantum capacity
Quantum circuit
Quantum sort
Cite
Citations (0)
In the process of implementing a quantum algorithm as a quantum circuit, the error rate of an actual quantum computer should be considered. In this paper, we confirm through simulation that the one control qubit quantum phase estimation algorithm performs better than the many control qubit quantum phase estimation algorithm on the noisy quantum processor. We use QISKit to simulate a quantum phase estimation algorithm. We performed the simulation considering the error rate of the IBM Q quantum processor. The error rate of the one control qubit quantum phase estimation algorithm is compared with the many control qubit quantum phase estimation algorithm.
Quantum Fourier transform
Quantum circuit
One-way quantum computer
Cite
Citations (3)
The variational quantum imaginary time evolution algorithm is efficient in finding the ground state of a quantum Hamiltonian. This algorithm involves solving a system of linear equations in a classical computer and the solution is then used to propagate a quantum wavefunction. Here, we show that owing to the noisy nature of current quantum processors, such a quantum algorithm or the family of quantum algorithms that require classical computation of inverting a matrix with high condition number will require single- and two-qubit gates with very low error probability. Failure to meet such condition will result in erroneous quantum data propagation even for a relatively small quantum circuit ansatz. Specifically, we find the upper bounds on how the quantum algorithmic error scales with the probability of errors in quantum hardware. Our work challenges the mainstream notion of hybrid quantum-classical quantum algorithms being able to perform under noisy environments while we show such algorithms in fact require very low error quantum gates to get reliable results.
Cite
Citations (0)
This chapter reviews the general problems and the high-level operation of the major quantum algorithms. It describes some of the quantum algorithms in more detail. These algorithms include: Deutsch algorithm, Deutsch–Jozsa algorithm, Simon's algorithm, Shor's algorithm, quantum phase estimation algorithm, Grover's Quantum Search Algorithm (QSA), Boyer–Brassard–Høyer–Tapp QSA, Dürr–Høyer QSA, quantum counting algorithm, quantum heuristic algorithm, quantum genetic algorithm, Harrow–Hassidim–Lloyd algorithm, quantum mean algorithm, and quantum weighted sum algorithm. The chapter provides more physical insights into some of the algorithms. Quantum computation is based on quantum interference, which is a dynamical process that allows one to evolve initial quantum states (inputs) into final states (outputs) by modifying intermediate multi-particle superpositions in some prescribed way. The chapter illustrates how interference patterns lead to computational problems that are well suited to quantum computations, by presenting the first such problem that was proposed by David Deutsch.
Quantum sort
Quantum Fourier transform
Cite
Citations (2)
A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.
Quantum sort
Quantum circuit
Quantum Fourier transform
Cite
Citations (0)
Contemporarily, quantum computing is one of the hottest research fields. Many quantum algorithms are proposed in order to utilize the power of quantum computers. Grover’s searching algorithm is one of them. In this article, by comparing a classical searching algorithm and Grover’s algorithm in the problem of finding a number in a finite database, the advantages of the latter are discussed. The actual quantum circuit to solve the problem is built and run on both a simulator and a real quantum computer. According to the analysis, Grover’s algorithm provides speedup in a searching task compared to the classical algorithm. However, noises in today’s quantum devices make the result of the quantum algorithm unreliable. In searching for multiple numbers, Grover’s algorithm has its shortcomings. Nevertheless, noises in quantum computing need to be addressed in order to utilize the potential of quantum computers in solving difficult problems. These results shed light on guiding further exploration of quantum algorithms and quantum computing.
Quantum sort
Speedup
Cite
Citations (1)