Quantum phase estimation algorithm

Last updated

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. [1] [2] :246

Contents

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm, [2] :131 the quantum algorithm for linear systems of equations, and the quantum counting algorithm.

Overview of the algorithm

The algorithm operates on two sets of qubits, referred to in this context as registers. The two registers contain and qubits, respectively. Let be a unitary operator acting on the -qubit register. The eigenvalues of a unitary operator have unit modulus, and are therefore 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 .

The goal is producing a good approximation for with a small number of gates and a high probability of success. The quantum phase estimation algorithm achieves this assuming oracular access to , and having available as a quantum state. This means that when discussing the efficiency of the algorithm we only worry about the number of times needs to be used, but not about the cost of implementing itself.

More precisely, the algorithm returns with high probability an approximation for , within additive error , using qubits in the first register, and controlled-U operations. Furthermore, we can improve the success probability to for any by using a total of uses of controlled-U, and this is optimal. [3]

Detailed description of the algorithm

The circuit for quantum phase estimation. PhaseCircuit.svg
The circuit for quantum phase estimation.

State preparation

The initial state of the system is:

where is the -qubit state that evolves through . We first apply the n-qubit Hadamard gate operation on the first register, which produces the state:Note that here we are switching between binary and -ary representation for the -qubit register: the ket on the right-hand side is shorthand for the -qubit state , where is the binary decomposition of .

Controlled-U operations

This state is then evolved through the controlled-unitary evolution whose action can be written asfor all . This evolution can also be written concisely aswhich highlights its controlled nature: it applies to the second register conditionally to the first register being . Remembering the eigenvalue condition holding for , applying to thus giveswhere we used .

To show that can also be implemented efficiently, observe that we can write , where denotes the operation of applying to the second register conditionally to the -th qubit of the first register being . Formally, these gates can be characterized by their action asThis equation can be interpreted as saying that the state is left unchanged when , that is, when the -th qubit is , while the gate is applied to the second register when the -th qubit is . The composition of these controlled-gates thus giveswith the last step directly following from the binary decomposition .

From this point onwards, the second register is left untouched, and thus it is convenient to write , with the state of the -qubit register, which is the only one we need to consider for the rest of the algorithm.

Apply inverse quantum Fourier transform

The final part of the circuit involves applying the inverse quantum Fourier transform (QFT) on the first register of :The QFT and its inverse are characterized by their action on basis states asIt follows that

Decomposing the state in the computational basis as the coefficients thus equalwhere we wrote with is the nearest integer to . The difference must by definition satisfy . This amounts to approximating the value of by rounding to the nearest integer.

Measurement

The final step involves performing a measurement in the computational basis on the first register. This yields the outcome with probabilityIt follows that if , that is, when can be written as , one always finds the outcome . On the other hand, if , the probability readsFrom this expression we can see that when . To see this, we observe that from the definition of we have the inequality , and thus: [4] :157 [5] :348

We conclude that the algorithm provides the best -bit estimate (i.e., one that is within of the correct answer) of with probability at least . By adding a number of extra qubits on the order of and truncating the extra qubits the probability can increase to . [5]

Toy examples

Consider the simplest possible instance of the algorithm, where only qubit, on top of the qubits required to encode , is involved. Suppose the eigenvalue of reads , . The first part of the algorithm generates the one-qubit state . Applying the inverse QFT amounts in this case to applying a Hadamard gate. The final outcome probabilities are thus where , or more explicitly,Suppose , meaning . Then , , and we recover deterministically the precise value of from the measurement outcomes. The same applies if .

If on the other hand , then , that is, and . In this case the result is not deterministic, but we still find the outcome as more likely, compatibly with the fact that is close to 1 than to 0.

More generally, if , then if and only if . This is consistent with the results above because in the cases , corresponding to , the phase is retrieved deterministically, and the other phases are retrieved with higher accuracy the closer they are to these two.

See also

Related Research Articles

<span class="mw-page-title-main">Pauli matrices</span> Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three 2 × 2 complex matrices that are traceless, Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

<span class="mw-page-title-main">Schrödinger equation</span> Description of a quantum-mechanical system

The Schrödinger equation is a partial differential equation that governs the wave function of a quantum-mechanical system. Its discovery was a significant landmark in the development of quantum mechanics. It is named after Erwin Schrödinger, who postulated the equation in 1925 and published it in 1926, forming the basis for the work that resulted in his Nobel Prize in Physics in 1933.

In physics, the CHSH inequality can be used in the proof of Bell's theorem, which states that certain consequences of entanglement in quantum mechanics cannot be reproduced by local hidden-variable theories. Experimental verification of the inequality being violated is seen as confirmation that nature cannot be described by such theories. CHSH stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt, who described it in a much-cited paper published in 1969. They derived the CHSH inequality, which, as with John Stewart Bell's original inequality, is a constraint—on the statistical occurrence of "coincidences" in a Bell test—which is necessarily true if an underlying local hidden-variable theory exists. In practice, the inequality is routinely violated by modern experiments in quantum mechanics.

<span class="mw-page-title-main">Second quantization</span> Formulation of the quantum many-body problem

Second quantization, also referred to as occupation number representation, is a formalism used to describe and analyze quantum many-body systems. In quantum field theory, it is known as canonical quantization, in which the fields are thought of as field operators, in a manner similar to how the physical quantities are thought of as operators in first quantization. The key ideas of this method were introduced in 1927 by Paul Dirac, and were later developed, most notably, by Pascual Jordan and Vladimir Fock. In this approach, the quantum many-body states are represented in the Fock state basis, which are constructed by filling up each single-particle state with a certain number of identical particles. The second quantization formalism introduces the creation and annihilation operators to construct and handle the Fock states, providing useful tools to the study of the quantum many-body theory.

<span class="mw-page-title-main">Rabi cycle</span> Quantum mechanical phenomenon

In physics, the Rabi cycle is the cyclic behaviour of a two-level quantum system in the presence of an oscillatory driving field. A great variety of physical processes belonging to the areas of quantum computing, condensed matter, atomic and molecular physics, and nuclear and particle physics can be conveniently studied in terms of two-level quantum mechanical systems, and exhibit Rabi flopping when coupled to an optical driving field. The effect is important in quantum optics, magnetic resonance and quantum computing, and is named after Isidor Isaac Rabi.

<span class="mw-page-title-main">Quantum logic gate</span> Basic circuit in quantum computing

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

In quantum physics, the scattering amplitude is the probability amplitude of the outgoing spherical wave relative to the incoming plane wave in a stationary-state scattering process. At large distances from the centrally symmetric scattering center, the plane wave is described by the wavefunction

A qutrit is a unit of quantum information that is realized by a 3-level quantum system, that may be in a superposition of three mutually orthogonal quantum states.

Photon polarization is the quantum mechanical description of the classical polarized sinusoidal plane electromagnetic wave. An individual photon can be described as having right or left circular polarization, or a superposition of the two. Equivalently, a photon can be described as having horizontal or vertical linear polarization, or a superposition of the two.

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way or measurement-based quantum computer (MBQC) is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

In mathematics, vector spherical harmonics (VSH) are an extension of the scalar spherical harmonics for use with vector fields. The components of the VSH are complex-valued functions expressed in the spherical coordinate basis vectors.

Amplitude amplification is a technique in quantum computing which generalizes the idea behind Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and independently rediscovered by Lov Grover in 1998.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state into some number of approximately pure Bell pairs, using only local operations and classical communication.

<span class="mw-page-title-main">Kicked rotator</span>

The kicked rotator, also spelled as kicked rotor, is a paradigmatic model for both Hamiltonian chaos and quantum chaos. It describes a free rotating stick in an inhomogeneous "gravitation like" field that is periodically switched on in short pulses. The model is described by the Hamiltonian

Partial-wave analysis, in the context of quantum mechanics, refers to a technique for solving scattering problems by decomposing each wave into its constituent angular-momentum components and solving using boundary conditions.

In pure and applied mathematics, quantum mechanics and computer graphics, a tensor operator generalizes the notion of operators which are scalars and vectors. A special class of these are spherical tensor operators which apply the notion of the spherical basis and spherical harmonics. The spherical basis closely relates to the description of angular momentum in quantum mechanics and spherical harmonic functions. The coordinate-free generalization of a tensor operator is known as a representation operator.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

The quantum Fisher information is a central quantity in quantum metrology and is the quantum analogue of the classical Fisher information. It is one of the central quantities used to qualify the utility of an input state, especially in Mach–Zehnder interferometer-based phase or parameter estimation. It is shown that the quantum Fisher information can also be a sensitive probe of a quantum phase transition. The quantum Fisher information of a state with respect to the observable is defined as

In quantum computing, the variational quantum eigensolver (VQE) is a quantum algorithm for quantum chemistry, quantum simulations and optimization problems. It is a hybrid algorithm that uses both classical computers and quantum computers to find the ground state of a given physical system. Given a guess or ansatz, the quantum processor calculates the expectation value of the system with respect to an observable, often the Hamiltonian, and a classical optimizer is used to improve the guess. The algorithm is based on the variational method of quantum mechanics.

References

  1. Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv: quant-ph/9511026 .
  2. 1 2 Nielsen, Michael A. & Isaac L. Chuang (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN   978-0521635035.
  3. Mande, Nikhil S.; Ronald de Wolf (2023). "Tight Bounds for Quantum Phase Estimation and Related Problems". arXiv: 2305.04908 [quant-ph].
  4. Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN   978-9812388582.
  5. 1 2 Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969): 339–354. arXiv: quant-ph/9708016 . Bibcode:1998RSPSA.454..339C. doi:10.1098/rspa.1998.0164. S2CID   16128238.