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.
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.
Quantum computing has received wide-spread attention lately due the possibility of a near-term breakthrough of quantum supremacy. This course acts as an introduction to the area of quantum computing.
Today one is able to manipulate matter at the nanoscale were quantum behavior becomes important and possibly information processing will have to take into account laws of quantum physics. We introduce
Logic synthesis describes techniques to map complex functionality into a sequence of a few, simple, and small logic primitives. It finds application dominantly in digital design, but is most recently
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith.
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on 2m real numbers (or complex, or hypercomplex numbers, although the Hadamard matrices themselves are purely real). The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.
Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.
Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...
Quantum computing has made significant progress in recent years, with Google and IBM releasing quantum computers with 72 and 50 qubits, respectively. Google has also achieved quantum supremacy with its 54-qubit device, and IBM has announced the release of ...
EPFL2023
Under magnetic fields, quantum magnets often undergo exotic phase transitions with various kinds of order. The discovery of a sequence of fractional magnetization plateaus in the Shastry-Sutherland compound SrCu2(BO3)(2) has played a central role in the hi ...