Skip to content

Quantum linear algebra

At a high level of abstraction, quantum computers compose unitary matrices, and do so with classically unparalleled efficiency. This hints at quantum speedups for linear algebra tasks. However, often one needs to work with large non-unitary matrices; thus, for performing general linear algebra tasks we often wish to embed certain non-unitary matrices into unitary matrices represented by efficient quantum circuits, and then apply them to quantum states, take their sums or products, or implement more general matrix functions. These tasks are collectively referred to as "quantum linear algebra," the building blocks of which are discussed in this section.

The techniques described in this section evolved over the past decades and converged to the presented unified framework within several distinct research threads. Block-encodings emerged as a natural approach for embedding non-unitary matrices into quantum circuits, inspired by approaches based on purification, dilation,1 and postselection. Quantum signal processing (QSP) was discovered as a byproduct of the characterization of simple single-qubit pulse sequences used in nuclear magnetic resonance [1], for synthesizing polynomial transformations applicable to a "signal parameter" encoded as a matrix element of a single-qubit rotation matrix. Meanwhile, it was extensively studied how matrix functions could be synthesized using the linear combinations of unitaries technique on matrix exponentials implemented by Hamiltonian simulation [2, 3, 4], or Chebyshev polynomials of operators implemented via quantum walk techniques [5, 6, 7]. Such matrix exponentials or Chebyshev polynomials can be implemented, e.g., via qubitization of a block-encoded operator. In parallel to progress on advanced amplitude amplification [8, 9] techniques, it was recognized [10, 11] that QSP can be "lifted" for applying polynomial transformations to the eigenvalues of quantum walk operators (such as those implemented by qubitization), and thus for implementing a rich family of matrix functions, immediately yielding an optimal algorithm for time-independent Hamiltonian simulation. The concepts of qubitization and QSP were later generalized and unified into the framework of quantum singular value transformation [12], providing generalizations and more efficient implementations of a number of existing quantum algorithms and leading to the discovery of several new algorithms.

Bibliography

  1. Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6(4):041067, 2016. arXiv: https://arxiv.org/abs/1603.03996. doi:10.1103/PhysRevX.6.041067.

  2. Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12(11&12):901–924, 2012. arXiv: https://arxiv.org/abs/1202.5822. doi:10.26421/QIC12.11-12.

  3. 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.

  4. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 33:1–33:14. 2019. arXiv: https://arxiv.org/abs/1804.01973. doi:10.4230/LIPIcs.ICALP.2019.33.

  5. 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.

  6. 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.

  7. Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017. arXiv: https://arxiv.org/abs/1511.02306. doi:10.1137/16M1087072.

  8. Lov K. Grover. Fixed-point quantum search. Physical Review Letters, 95(15):150501, 2005. arXiv: https://arxiv.org/abs/quant-ph/0503205. doi:10.1103/PhysRevLett.95.150501.

  9. 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.

  10. Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical Review Letters, 118(1):010501, 2017. arXiv: https://arxiv.org/abs/1606.02685. doi:10.1103/PhysRevLett.118.010501.

  11. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv: https://arxiv.org/abs/1610.06546. doi:10.22331/q-2019-07-12-163.

  12. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 193–204. 2019. arXiv: https://arxiv.org/abs/1806.01838. doi:10.1145/3313276.3316366.

  13. Michael M. Wolf. Quantum channels & operations: guided tour. 2012. https://mediatum.ub.tum.de/download/1701036/1701036.pdf, accessed: 2023-09-30. URL: https://mediatum.ub.tum.de/download/1701036/1701036.pdf.

  14. Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2nd edition, 2017. arXiv: https://arxiv.org/abs/1106.1445. doi:10.1017/9781316809976.

  1. That is, representing an incoherent state or operation as a coherent one with the help of an ancillary system—see for example Stinespring representation [13] or Stinespring dilation [14]. ↩