Concept

Quantum phase estimation algorithm

Summary
In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by Alexei Kitaev in 1995. Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm, the quantum algorithm for linear systems of equations, and the quantum counting algorithm. Let be a unitary operator acting on an -qubit register. Unitarity implies that all the eigenvalues of have unit modulus, and can therefore be characterized by their phase. Thus if is an eigenvector of , then for some . Due to the periodicity of the complex exponential, we can always assume . Our goal is to find a good approximation to with a small number of gates and with high probability. The quantum phase estimation algorithm achieves this under the assumptions of having oracular access to , and having available as a quantum state. More precisely, the algorithm returns an approximation for , with high probability within additive error , using qubits (without counting the ones used to encode the eigenvector state) and controlled-U operations. The input consists of two registers (namely, two parts): the upper qubits comprise the first register, and the lower qubits are the second register. The initial state of the system is: After applying n-bit Hadamard gate operation on the first register, the state becomes: Let be a unitary operator with eigenvector such that . Thus, Overall, the transformation implemented on the two registers by the controlled gates applying isThis can be seen by the decomposition of into its bitstring and binary representation , where . Clearly, becomesEach will only apply if the qubit is , implying that it is controlled by that bit.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.