Quantum phase estimation: the precision bound and its cost

Definition

Quantum phase estimation estimates the phase φ in an eigenvalue e^(2πiφ) of a unitary operator U. Kitaev's measurement, and the circuit of Cleve and coauthors, are given an eigenstate of U and a way to apply controlled powers of U. Kitaev's 1995 paper introduces the procedure as a measurement of that phase and uses it inside a polynomial quantum algorithm for the Abelian stabilizer problem, which includes factoring and the discrete logarithm. Cleve, Ekert, Macchiavello, and Mosca give the circuit usually taught under this name: controlled powers U^(2^k) on an ancilla register, followed by an inverse quantum Fourier transform.

The routine does not, by itself, print a classical list of entries of an arbitrary matrix. The eigenstate has to be prepared, and the controlled powers have to be gates the machine can run. Those two assumptions are where later applications either pay a stated cost or stop.

The explicit factoring bound this library quotes remains the one in Shor's algorithm, from the 1997 paper. Kitaev's stabilizer algorithm is a polynomial-time result proved by a different method. It is not a replacement for that gate count.

Intuition

One controlled application of U, with the control qubit in superposition, writes the eigenvalue onto the control and leaves the eigenstate alone. Kitaev's measurement operator applies a Hadamard, the controlled-U, and a second Hadamard. The probability of reading 1 on the control is one half times (1 minus the cosine of 2πφ). Repeating the measurement estimates that cosine. Replacing U by iU replaces the cosine with minus the sine, and the two estimates locate φ. For any fixed precision, Lemma 9 of that paper does this with error probability at most ε in a number of operations on the order of log(1/ε), in a gate set that includes controlled-U.

Fixed precision is not enough for order-finding. If the computer can apply controlled-U^(2^j), the same one-bit measurement estimates the fractional part of 2^j φ. Lemma 10 stitches those estimates into a finer phase. Cleve and coauthors prepare, in one register, the Fourier state whose amplitude on basis state y is the phase factor e^(2πiφy), then invert the Fourier transform. When φ is an exact multiple of 1/2^m, the measurement returns those bits with certainty. When it is not, the closest m-bit string is still the most likely outcome.

Shor's algorithm is the case where U multiplies by a fixed base modulo an integer. The order appears as the phase. The 1997 paper writes the Fourier transform on the exponent register directly. Cleve and coauthors, in their section 6, retell order-finding in the phase-estimation language and are explicit about the state that makes the retelling work. An eigenvector of modular multiplication is not what the algorithm prepares. It prepares a uniform superposition, which is a superposition of those eigenvectors, and continued fractions recover the order from the measured phase. The phase estimation glossary entry is the short form of that distinction.

Complexity

This is a count of calls to a supplied unitary, plus the gates of the Fourier transform or of Kitaev's measurements. It is not an oracle query bound, and it is not a gate count for an arbitrary Hamiltonian.

Lemma 10 is the bound this page quotes for Kitaev's measurement. Let l be a positive integer and set r = 2^l − 1. For any error probability ε, the phase can be measured to precision 2^(−l−2), with error probability at most ε, by an operation sequence of length O(l log(l/ε)) plus a term polynomial in l. The sequence is allowed to use the gate that applies U^a for a control value a between 0 and r. That gate is used at most O(l log(l/ε)) times. When U is a permutation of bit strings of length n, and every cycle is therefore of length at most 2^n, Theorem 1 of the same paper recovers the exact rational phase. It is enough to measure to precision 2^(−2n−1) and then run continued fractions. The powered gate running up to exponent 2^(2n) is used O(n log(n/ε)) times, inside a sequence of length polynomial in n plus O(n) log(1/ε), with error probability at most ε.

Cleve, Ekert, Macchiavello, and Mosca count the inverse-Fourier circuit differently. Section 5 assumes devices for controlled-U, controlled-U^2, controlled-U^4, and so on, and one copy of the eigenstate. The network uses m of those controlled powers and O(m^2) other gates. If φ is not a multiple of 1/2^m, the inverse Fourier transform returns the closest m-bit approximation, which lies at most 1/2^(m+1) away from φ, with probability at least 4/π². They record that constant as 0.405. Appendix C spends extra bits to raise the probability. An estimate within 1/2^(n+1) of φ, with probability at least 1 − δ, uses a register of m bits where m is n plus the ceiling of the base-2 logarithm of (1/(2δ) + 1/2). Here n is the number of bits of precision they asked for, not the number of qubits U acts on. The extra bits are a logarithmic overhead in 1/δ.

Neither bound cancels the cost of building the controlled powers. If each controlled-U^(2^j) is a long circuit, the lemma counts calls to that circuit, and the calls dominate. In the order-finding application, Cleve and coauthors note that a controlled power of modular multiplication on an n-bit modulus can be implemented with O(n^2) elementary gates, and that 2n bits of the phase suffice to extract the order. They also note that they know no straightforward efficient preparation of a single eigenvector, which is why the algorithm estimates a random eigenphase inside a superposition and checks the candidate classically.

Applications and limits

Abrams and Lloyd apply the Fourier method to a Hamiltonian by estimating eigenvalues of a time-evolution operator. The letter states the hypothesis in the first pages. The machine can prepare an approximate eigenvector whose squared overlap with a true eigenvector is not exponentially small, meaning the overlap is at least an inverse polynomial in the problem size, and the evolution operator can be implemented in quantum polynomial time. Under that hypothesis, the eigenvector and its eigenvalue can be found in time proportional to the reciprocal of the squared overlap and to the reciprocal of the requested accuracy. Once the cost of simulating the evolution is included, they conclude that the number of operations scales as the inverse square of that accuracy. The abstract says that classically intractable problems from atomic physics may be solvable with between 50 and 100 qubits. In the body, a boron example in an orbital basis is about 60 qubits, and an accounting that moves electron pairs into a position basis for the Coulomb interaction reaches about 100. They describe a brute-force implementation of the two-electron operators as likely to remain intractable. Read the range as their estimate under those choices of basis, not as a qubit count for chemistry in general. The abstract compares the quantum runtime with all known classical algorithms for the cases they have in mind. It does not prove that no classical polynomial algorithm exists.

The chemistry proposal already in this library is Aspuru-Guzik, Dutoi, Love, and Head-Gordon (2005): prepare an approximate ground state, simulate the molecular Hamiltonian, and read the phase. That is phase estimation under the overlap and simulation hypotheses, specialized to a molecule. VQE is the later algorithm that drops the long coherent evolution and estimates an expectation value instead. The comparison is a difference in what is proved. Phase estimation has a precision and a failure probability once the eigenstate and the powers are granted. VQE has a variational upper bound and no proved time to the ground state.

Chemistry is where this library keeps that comparison. The HHL algorithm is the linear-systems application. It calls phase estimation, and its output is a quantum state rather than a classical list of solution entries. The runtime and the dequantization caveat are on that page, not theorems of this one. The controlled powers are an application of Hamiltonian simulation. The cost of building those powers is a theorem of that page, in whatever access model the Hamiltonian was given. Amplitude estimation is discussed with amplitude amplification, not as a separate algorithm page. Linear systems is the stub that holds the comparison.

Reading the source

Read Kitaev's section 3 for the measurement, and Lemma 10 and Theorem 1 for the bounds quoted above. Read Cleve, Ekert, Macchiavello, and Mosca, section 5 and Appendix C, for the inverse-Fourier circuit and the 4/π² probability, and section 6 before teaching order-finding as phase estimation. Read Abrams and Lloyd for the overlap hypothesis before quoting a speedup for eigenvalues of a Hamiltonian. Aspuru-Guzik et al. is the molecular-energy proposal. The VQE page is the account of what was done when that proposal's coherence was the obstacle.