Skip to content

Amplitude amplification

Rough overview (in words)

Given a quantum subroutine that succeeds with a probability less than 1, amplitude amplification can be used to boost the success probability to 1 by making repeated calls to the subroutine and to a unitary that determines if the subroutine has succeeded. Amplitude amplification can be viewed as a generalization of Grover's search algorithm [1] and offers a quadratic speedup compared to classical methods in many instances.

Rough overview (in math)

We are given an initial state \(\ket{\psi_0}\), a target state \(\ket{\psi_g}\) that we can mark (i.e., the ability to reflect about the state), and a unitary \(U\) (and its inverse \(U^\dag\)) such that

\[\begin{equation} U\ket{\psi_0} = \ket{\psi} = a \ket{\psi_g} + b\ket{\psi_b}\label{eq:U=a+b} \end{equation}\]

where \(\ket{\psi_b}\) is a state orthogonal to the target state. In other words, \(|a|^2\) is the probability of success of applying \(U\) and measuring \(\ket{\psi_g}\). In addition, we are given the ability to implement the reflection operator around the initial state \(R_{\psi_0} = I - 2\ket{\psi_0}\bra{\psi_0}\) and an operation that, when restricted to the subspace spanned by \(\{ \ket{\psi_g}, \ket{\psi_b} \}\), acts as the reflection around the target state \(R_{\psi_g} = I - 2\ket{\psi_g}\bra{\psi_g}\).

Then, amplitude amplification allows us to boost the success probability to 1 through repeated calls to an operator \(W = - U R_{\psi_0} U^\dag R_{\psi_g}\), from the initial state \(U \ket{\psi_0} = \ket{\psi}\). The standard analysis [2] proceeds by letting \(a=\sin(\theta)\) and \(b=\cos(\theta)\), and showing that the 2D subspace spanned by \(\ket{\psi_g}, \ket{\psi_b}\) is invariant under \(W\), which acts as a rotation operator such that \(\ket{\psi_g}\bra{\psi_g} W^m \ket{\psi} = \sin((2m+1)\theta) \ket{\psi_g}\).

The algorithm can also be viewed through the lens of quantum singular value transformation (QSVT) whereby \(U\) provides a generalized block-encoding (known as a projected unitary encoding) of the amplitude \(a\). We can see this from \(\ket{\psi_g}\bra{\psi_g} U \ket{\psi_0}\bra{\psi_0} = a\ket{\psi_g}\bra{\psi_0}\). We choose to apply a polynomial \(f(\cdot)\) satisfying the quantum signal processing conditions and \(f(a)=1\) to the block-encoded amplitude [3, Theorem 27 & 28]. For example, the textbook version of amplitude amplification is recovered by setting the QSVT rotation angles to \(\pm \frac{\pi}{2}\).1 This QSVT circuit applies a degree \(2m+1\) Chebyshev polynomial of the first kind \(T_{2m+1}\) to the amplitude \(a\), such that \(\ket{\psi_g}\bra{\psi_g} W^m \ket{\psi} = T_{2m+1}(a) \ket{\psi_g} = (-1)^m \sin((2m+1)\theta) \ket{\psi_g}\) for \(a=\sin(\theta)\).

Dominant resource cost (gates/qubits)

The number of calls to \(W\) is \(m = \frac{\pi}{4\arcsin(a)} - \frac{1}{2} = \mathcal{O}\left( 1/a \right)\) for small \(a\). Each call to \(W\) requires a call to each of \(U, U^\dag, R_{\psi_0}, R_{\psi_g}\). Often we have \(\ket{\psi_0} = \ket{\bar{0}}\), and \(U\) acts on \(n\) register qubits and \(k\) ancilla qubits such that \(U\ket{\bar{0}} = a\ket{\psi_g}_n\ket{\bar{0}}_k + b \ket{\perp}_{n,k}\), where \(\ket{\perp}_{n,k}\) denotes a state orthogonal to \(\ket{\bar{0}}_k\). In this case the reflection operators are simple to implement using multi-controlled Toffoli gates.

Caveats

The textbook version of amplitude amplification assumes that the success amplitude \(a\) exactly equals \(\sin\left(\pi/(4m+2)\right)\) for an integer \(m\). If this is not the case (e.g., when \(a= 1/\sqrt{2}\)), we can introduce a new qubit in \(\ket{0}\) and apply an \(R_y(2\phi)\) gate to reduce the success probability (now defined by measuring \(\ket{\psi_g}\ket{0}\)) to \(a \cos(\phi) = \sin\left(\pi/(4m'+2) \right)\) for an integer \(m'\).

In cases where we can only lower bound the success amplitude \(a \ge a_0\), it is common to use fixed-point amplitude amplification [4]. This is best understood through QSVT [3, Theorem 27], where the reflection operators are replaced by parametrized phase operators \(e^{i \theta \ket{\psi_g}\bra{\psi_g}}\) and \(e^{i \phi \ket{\psi_0}\bra{\psi_0}}\) (it is shown in [5, Section 8.5] how these phase operators can be constructed using the corresponding controlled reflection operator. If only the uncontrolled reflection is available, a control can be added using e.g., [6, Fig.5]). The QSVT rotation angles are chosen to implement a polynomial that maps all amplitudes taking value at least \(a_0\) to at least \((1-\epsilon)\). The fixed-point amplitude amplification circuit uses a QSVT circuit that makes \(\mathcal{O}\left( \frac{1}{a_0} \log\left(\frac{1}{\epsilon}\right) \right)\) calls to \(U, U^\dag, e^{i \theta \ket{\psi_g}\bra{\psi_g}}\) and \(e^{i \phi \ket{\psi_0}\bra{\psi_0}}\).

Example use cases

Further reading

  • Both amplitude amplification and Grover search can be viewed through the lens of quantum walks on suitably constructed graphs. The quantum walks also take the form of a product of two reflections and more generally can be understood as quantizing a Markov chain describing a classical random walk [8]. We refer the interested reader to [9, 10, 11, 12].
  • Oblivious amplitude amplification: Amplitude amplification can be extended to the case of oblivious amplitude amplification (OAA) [13]. The original formulation considered a setting where one is given unitary \(U\) such that for any state \(\ket{\psi}\), we have
    \[\begin{align} U \ket{\bar{0}_m} \ket{\psi} = a \ket{\bar{0}_m} V \ket{\psi} + b \ket{\bar{0}_m^\perp \phi} \end{align}\]

    for a unitary operator \(V\). The goal is to amplify the probability for the state \(\ket{\bar{0}_m} V \ket{\psi}\) to 1. This is achieved through \(\mathcal{O}\left( 1/a \right)\) applications of an operator \(W = U (I - 2\ket{\bar{0}_m}\bra{\bar{0}_m}) U^\dag (I - 2\ket{\bar{0}_m}\bra{\bar{0}_m})\) applied to \(U \ket{\bar{0}_m} \ket{\psi}\). We see that \(W\) does not require reflections around the initial state \(\ket{\psi}\). We can recognize \(U\) as an \(m\)-qubit block-encoding of the operator \(a V\), which can be transformed to a block-encoding of \(V\) using quantum singular value transformation (QSVT).2 The OAA subroutine is used in the context of Hamiltonian simulation via Taylor series, where it would be problematic to have to reflect around the initial state during amplification.3 It is also used in [14] (applied to isometries) for simulation of open quantum systems. OAA requires the block-encoded operator being amplified to preserve state norms (i.e. it must be an isometry), as this ensures that the success probability of the operation is independent of the state to which it is applied, which in turn enables amplification without reflection around the initial state. While a block-encoding of a non-isometric operator \(A\) can also be amplified using QSVT [3, Theorem 30],[15], it is not possible to boost the success probability of applying \(A\) to unity for all input states. In the worst case, the success probability can be improved from \(\sigma_{\mathrm{min}}^2\) to \(\sigma_{\mathrm{min}}^2/\sigma_{\mathrm{max}}^2\), where \(\sigma_{\mathrm{min}}, \sigma_{\mathrm{max}} \in [0,1]\) are the smallest and largest singular values of \(A\). As a result, to boost the success probability of applying \(A\) to unity for a general input state, we require regular amplitude amplification, involving reflections around the initial state. - While we are unaware of a standard reference for the "exact\" version of amplitude amplification using an additional ancilla qubit, discussed in the caveats above, it is explained more fully in these video lectures and also in [16, Appendix A].

Bibliography

  1. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC), 212–219. 1996. arXiv: https://arxiv.org/abs/quant-ph/9605043. doi:10.1145/237814.237866.

  2. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. doi:10.1090/conm/305/05215.

  3. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics [full version]. arXiv: https://arxiv.org/abs/1806.01838, 2018.

  4. Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. Physical Review Letters, 113(21):210501, 2014. arXiv: https://arxiv.org/abs/1409.3305. doi:10.1103/PhysRevLett.113.210501.

  5. Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv: https://arxiv.org/abs/2201.08309, 2022.

  6. John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand unification of quantum algorithms. Physical Review X, 2(4):040203, 2021. arXiv: https://arxiv.org/abs/2105.02859. doi:10.1103/PRXQuantum.2.040203.

  7. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum sdp-solvers: better upper and lower bounds. Quantum, 4:230, 2020. Earlier version in FOCS'17. arXiv: https://arxiv.org/abs/1705.01843. doi:10.22331/q-2020-02-14-230.

  8. Márió Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), 32–41. 2004. arXiv: https://arxiv.org/abs/quant-ph/0401053. doi:10.1109/FOCS.2004.53.

  9. Andrew M. Childs. Lecture notes on quantum algorithms. 2022. http://www.cs.umd.edu/~amchilds/qa/, accessed: 2023-05-17.

  10. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142–164, 2011. Earlier version in STOC'07. arXiv: https://arxiv.org/abs/quant-ph/0608026. doi:10.1137/090745854.

  11. Simon Apers, András Gilyén, and Stacey Jeffery. A unified framework of quantum walk search. In Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS), 6:1–6:13. 2021. arXiv: https://arxiv.org/abs/1912.04233. doi:10.4230/LIPIcs.STACS.2021.6.

  12. András Gilyén. Quantum walk based search methods and algorithmic applications. Master's thesis, Eötvös Loránd University, 2014. URL: http://web.cs.elte.hu/blobs/diplomamunkak/msc\_mat/2014/gilyen\_andras\_pal.pdf.

  13. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse hamiltonians. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), 283–292. 2014. arXiv: https://arxiv.org/abs/1312.1414. doi:10.1145/2591796.2591854.

  14. Richard Cleve and Chunhao Wang. Efficient quantum algorithms for simulating lindblad evolution. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 17:1–17:14. 2017. arXiv: https://arxiv.org/abs/1612.09512. doi:10.4230/LIPIcs.ICALP.2017.17.

  15. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv: https://arxiv.org/abs/1707.05391, 2017.

  16. Sam McArdle, András Gilyén, and Mario Berta. Quantum state preparation without coherent arithmetic. arXiv: https://arxiv.org/abs/2210.14892, 2022.

  17. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Physical Review Letters, 114(9):090502, 2015. arXiv: https://arxiv.org/abs/1412.4687. doi:10.1103/PhysRevLett.114.090502.

  18. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), 792–809. 2015. arXiv: https://arxiv.org/abs/1501.01715. doi:10.1109/FOCS.2015.54.

  1. These rotation angles enable a gate compilation that removes the need for the QSVT ancilla qubit. ↩

  2. We note that in this interpretation, one may be concerned that the phase information of the unitary \(V\) is lost by transforming the singular values. This turns out not to be problematic, as the phase information of \(V\) can be considered stored in the basis transformation matrices present in the singular value decomposition, rather than in the diagonal singular values matrix. This is taken care of automatically using QSVT. Phases are preserved when using an odd polynomial. ↩

  3. More precisely, a robust version of OAA is used which is applicable to an operator that is \(\epsilon\) close to being unitary [17, 18]. ↩