A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. A quantum system can undergo two types of operation, measurement and quantum state transformation, operations themselves must be unitary (reversible). Most quantum algorithms involve a series of quantum state transformations followed by a measurement. Currently very few quantum algorithms are known and no general design methodology exists for their construction.
A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. A quantum system can undergo two types of operation, measurement and quantum state transformation, operations themselves must be unitary (reversible). Most quantum algorithms involve a series of quantum state transformations followed by a measurement. Currently very few quantum algorithms are known and no general design methodology exists for their construction.
The difference between classical and quantum algorithms (QA) is following: problem solved by QA is coded in the structure of the quantum operators. Input to QA in this case is always the same. Output of QA says which problem coded. In some sense, give a function to QA to analyze and QA returns its property as an answer without quantitative computing. QA studies qualitative properties of the functions. The core of any QA is a set of unitary quantum operators or quantum gates. In practical representation, quantum gate is a unitary matrix with particular structure. The size of this matrix grows exponentially with an increase in the number of inputs, which significantly limits the QA simulation on a classical computer with von Neumann architecture. Quantum search algorithm (QSA) - models apply for the solution of computer science problems as searching in unstructured data base, quantum cryptography, engineering tasks, control system design, robotics, smart controllers, etc. Grovers algorithm is explained in details along with implementations on a local computer simulator. The presented article describes a practical approach to modeling one of the most famous QA on classical computers, the Grover algorithm.
Quantum computing is a system of computation that exploits the quantum-mechanical nature of reality at nano-scales in order to perform certain operations in a way that can scale better than is possible with classical computing. While the hardware sideof quantum computing is still in its infancy, many quantum algorithms - sets of instructions to run on a quantum computer in order to complete particular tasks - have been designed and analyzed. One of the most famous of these is Grover’s algorithm, an algorithm for searching a database. Two types of generalizations of Grover’s algorithm have been studied: spatial search algorithms (algorithms for searching discrete spaces) and “analog” search algorithms (algorithms performed by the evolution of physical systems). We develop and analyze algorithms that are generalizations of both those generalizations – an analog search algorithm for searching continuous, rather than discrete, spaces.
Grover's quantum search algorithm is an important landmark discovery in the area of quantum computing that drives a quantum computer from a known initial state(source state) to an unknown final state(target state) by using selective phase inversions of these states. The algorithm is simply a successive iteration of the Grover's search operator, which is a product of selective inversion operators of source and target states. In its original form, Grover's operator performs the selective inversions only on a unique source state and a unique target state. In the generalized version, we make our search operator to perform selective inversions on more than one source and target states. First, we find that the case of selective inversions of two source and two target states can be easily analysed somewhat similar to the case of Grover's algorithm. But unlike Grover's operator, the selective inversions of three source and three target states is not so easy to study analytically and hence we perform numerical calculations on some specific cases. We find that these generalized search operators also give us a successful quantum search as expected.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
Abstract As computers get faster and faster, the size of the circuitry imprinted onto silicon chips decreases. The size of the circuitry becomes so small that its behavior is governed by the laws of quantum mechanics. Such a computer, whose computations would be fully quantum mechanical, is called a quantum computer. Any computational task such as addition, multiplication, displaying graphics, or updating databases is performed by a computer according to an algorithm — an abstract set of instructions. Quantum computers would accomplish tasks by performing quantum algorithms. A quantum algorithm is a sequence of unitary evolutions carried out on a quantum string made up of qubits, which can exist as a superposition of classical strings. This chapter discusses the computational complexity of a quantum algorithm, Deutsch's algorithm and its efficiency as quantified by the Holevo bound, Oracles, Grover's search algorithm, quantum factorisation, quantum Fourier transform, and phase estimation.
Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.