Block-encoding structured matrices for data input in quantum computing

Christoph Sünderhauf1, Earl Campbell1,2, and Joan Camps1

1Riverlane, St. Andrews House, 59 St. Andrews Street, Cambridge CB2 3BZ, United Kingdom
2Dept. of Physics and Astronomy, University of Sheffield, Sheffield S3 7RH, United Kingdom

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via $\textit{block encoding}$ circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.

Quantum computers promise to solve certain problems much, much faster than even the largest classical supercomputers. Data describing the problem to be solved must be loaded onto the quantum computer; this data loading can be a bottleneck, even thwarting the entire speed-up promised by quantum computation. A particularly widespread method of representing numerical data matrices on quantum computers is in the form of “block encodings”.

In this research article, we present a new set of schemes how data can be loaded into block encodings. Particularly, if the data matrices are structured, i.e. have a certain pattern and/or repeated data elements, our scheme shows how to make use of this structure in order to reduce the cost of data loading. We explain how to construct quantum circuits taking into account and optimising for such structured data. In the future, our work can help to load various data matrices into quantum computers for use in various quantum algorithms, making the most of the data’s structure to reduce the data loading bottleneck.

► BibTeX data

► References

[1] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge ; New York, 10th anniversary ed edition, 2010. ISBN 978-1-107-00217-3.

[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779), October 2019. ISSN 1476-4687. 10.1038/​s41586-019-1666-5. URL https:/​/​​articles/​s41586-019-1666-5.

[3] IBM. IBM Unveils Breakthrough 127-Qubit Quantum Processor, 2021. URL https:/​/​​2021-11-16-IBM-Unveils-Breakthrough-127-Qubit-Quantum-Processor.

[4] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127 (18): 180501, October 2021. ISSN 0031-9007, 1079-7114. 10.1103/​PhysRevLett.127.180501. URL http:/​/​​abs/​2106.14734. arXiv:2106.14734 [quant-ph].

[5] Scott Aaronson. How Much Structure Is Needed for Huge Quantum Speedups?, September 2022. URL http:/​/​​abs/​2209.06930. arXiv:2209.06930 [quant-ph].

[6] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan. Is there evidence for exponential quantum advantage in quantum chemistry?, November 2022. URL . arXiv:2208.02199 [physics, physics:quant-ph].

[7] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, June 2019. 10.1145/​3313276.3316366. URL http:/​/​​abs/​1806.01838. arXiv: 1806.01838.

[8] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand Unification of Quantum Algorithms. PRX Quantum, 2 (4): 040203, December 2021. 10.1103/​PRXQuantum.2.040203. URL https:/​/​​doi/​10.1103/​PRXQuantum.2.040203. Publisher: American Physical Society.

[9] Scott Aaronson. Read the fine print. Nature Physics, 11 (4), April 2015. ISSN 1745-2481. 10.1038/​nphys3272. URL https:/​/​​articles/​nphys3272.

[10] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng. Quantum Resources Required to Block-Encode a Matrix of Classical Data. arXiv, June 2022. URL . arXiv:2206.03505 [quant-ph].

[11] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. arXiv:1804.01973 [quant-ph], page 14 pages, 2019. 10.4230/​LIPIcs.ICALP.2019.33. URL http:/​/​​abs/​1804.01973. arXiv: 1804.01973.

[12] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100 (16): 160501, April 2008. ISSN 0031-9007, 1079-7114. 10.1103/​PhysRevLett.100.160501. URL http:/​/​​abs/​0708.1879. arXiv:0708.1879 [quant-ph].

[13] Connor T. Hann, Gideon Lee, S. M. Girvin, and Liang Jiang. Resilience of quantum random access memory to generic noise. PRX Quantum, 2 (2): 020311, April 2021. ISSN 2691-3399. 10.1103/​PRXQuantum.2.020311. URL http:/​/​​abs/​2012.05340. arXiv:2012.05340 [quant-ph].

[14] Quynh T. Nguyen, Bobak T. Kiani, and Seth Lloyd. Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra. Quantum, 6: 876, December 2022. 10.22331/​q-2022-12-13-876. URL https:/​/​​papers/​q-2022-12-13-876/​. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.

[15] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrice. arXiv:2203.10236 [quant-ph], March 2022. URL http:/​/​​abs/​2203.10236. arXiv: 2203.10236.

[16] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, July 2019. ISSN 2521-327X. 10.22331/​q-2019-07-12-163. URL http:/​/​​abs/​1610.06546. arXiv: 1610.06546.

[17] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X, 8 (4): 041015, October 2018. 10.1103/​PhysRevX.8.041015. URL https:/​/​​doi/​10.1103/​PhysRevX.8.041015. Publisher: American Physical Society.

[18] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. Quantum, 3: 208, December 2019. ISSN 2521-327X. 10.22331/​q-2019-12-02-208. URL http:/​/​​abs/​1902.02134. arXiv:1902.02134 [physics, physics:quant-ph].

[19] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. Even more efficient quantum computations of chemistry through tensor hypercontraction. PRX Quantum, 2 (3): 030305, July 2021. ISSN 2691-3399. 10.1103/​PRXQuantum.2.030305. URL http:/​/​​abs/​2011.03494. arXiv: 2011.03494.

[20] Aleksei V. Ivanov, Christoph Sünderhauf, Nicole Holzmann, Tom Ellaby, Rachel N. Kerber, Glenn Jones, and Joan Camps. Quantum Computation for Periodic Solids in Second Quantization, October 2022. URL . arXiv:2210.02403 [quant-ph].

[21] M. Szegedy. Quantum speed-up of Markov chain based algorithms. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 32–41, October 2004. 10.1109/​FOCS.2004.53. ISSN: 0272-5428.

[22] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, October 2015. 10.1109/​FOCS.2015.54. URL http:/​/​​abs/​1501.01715. arXiv:1501.01715 [quant-ph].

[23] Yuta Kikuchi, Conor Mc Keever, Luuk Coopmans, Michael Lubasch, and Marcello Benedetti. Realization of quantum signal processing on a noisy quantum computer. npj Quantum Information, 9 (1), September 2023. ISSN 2056-6387. 10.1038/​s41534-023-00762-0. URL http:/​/​​10.1038/​s41534-023-00762-0.

[24] Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52 (4): R2493–R2496, October 1995. ISSN 1050-2947, 1094-1622. 10.1103/​PhysRevA.52.R2493. URL https:/​/​​doi/​10.1103/​PhysRevA.52.R2493.

[25] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, September 2012. 10.1103/​PhysRevA.86.032324. URL https:/​/​​doi/​10.1103/​PhysRevA.86.032324. Publisher: American Physical Society.

[26] Sergei Bravyi and Alexei Kitaev. Universal Quantum Computation with ideal Clifford gates and noisy ancillas. arXiv:quant-ph/​0403025, December 2004. 10.1103/​PhysRevA.71.022316. URL http:/​/​​abs/​quant-ph/​0403025. arXiv: quant-ph/​0403025.

[27] Joe O'Gorman and Earl T. Campbell. Quantum computation with realistic magic state factories. Physical Review A, 95 (3): 032338, March 2017. ISSN 2469-9926, 2469-9934. 10.1103/​PhysRevA.95.032338. URL http:/​/​​abs/​1605.07197. arXiv:1605.07197 [quant-ph].

[28] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549 (7671): 172–179, September 2017. ISSN 0028-0836, 1476-4687. 10.1038/​nature23460. URL http:/​/​​abs/​1612.07330. arXiv: 1612.07330.

[29] Austin G. Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. arXiv:1808.06709 [quant-ph], August 2019. URL http:/​/​​abs/​1808.06709. arXiv: 1808.06709.

[30] Nick S. Blunt, Joan Camps, Ophelia Crawford, Róbert Izsák, Sebastian Leontica, Arjun Mirani, Alexandra E. Moylett, Sam A. Scivier, Christoph Sünderhauf, Patrick Schopf, Jacob M. Taylor, and Nicole Holzmann. Perspective on the Current State-of-the-Art of Quantum Computing for Drug Discovery Applications. Journal of Chemical Theory and Computation, 18 (12): 7001–7023, December 2022. ISSN 1549-9618. 10.1021/​acs.jctc.2c00574. URL https:/​/​​10.1021/​acs.jctc.2c00574. Publisher: American Chemical Society.

[31] Craig Gidney. Halving the cost of quantum addition. Quantum, 2: 74, June 2018. 10.22331/​q-2018-06-18-74. URL https:/​/​​papers/​q-2018-06-18-74/​. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.

[32] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization. PRX Quantum, 1 (2): 020312, November 2020. 10.1103/​PRXQuantum.1.020312. URL https:/​/​​doi/​10.1103/​PRXQuantum.1.020312. Publisher: American Physical Society.

[33] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T-gates for dirty qubits in state preparation and unitary synthesis, December 2018. URL http:/​/​​abs/​1812.00954. arXiv:1812.00954 [quant-ph] type: article.

[34] D.K Callebaut. Generalization of the cauchy-schwarz inequality. Journal of Mathematical Analysis and Applications, 12 (3): 491–494, 1965. ISSN 0022-247X. https:/​/​​10.1016/​0022-247X(65)90016-8. URL https:/​/​​science/​article/​pii/​0022247X65900168.

[35] Thomas G. Draper. Addition on a Quantum Computer. arXiv:quant-ph/​0008033, August 2000. URL http:/​/​​abs/​quant-ph/​0008033. arXiv: quant-ph/​0008033.

[36] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv:quant-ph/​0410184, October 2004. URL http:/​/​​abs/​quant-ph/​0410184. arXiv: quant-ph/​0410184.

[37] Lidia Ruiz-Perez and Juan Carlos Garcia-Escartin. Quantum arithmetic with the Quantum Fourier Transform. Quantum Information Processing, 16 (6): 152, June 2017. ISSN 1570-0755, 1573-1332. 10.1007/​s11128-017-1603-1. URL http:/​/​​abs/​1411.5949. arXiv:1411.5949 [quant-ph].

[38] A. Mahasinghe and J. B. Wang. Efficient quantum circuits for Toeplitz and Hankel matrices. Journal of Physics A: Mathematical and Theoretical, 49 (27): 275301, July 2016. ISSN 1751-8113, 1751-8121. 10.1088/​1751-8113/​49/​27/​275301. URL http:/​/​​abs/​1605.07710. arXiv:1605.07710 [quant-ph].

[39] Daan Camps and Roel Van Beeumen. FABLE: Fast Approximate Quantum Circuits for Block-Encodings. April 2022. URL . arXiv:2205.00081 [quant-ph].

[40] Mikko Mottonen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa. Quantum Circuits for General Multiqubit Gates. Physical Review Letters, 93 (13): 130502, September 2004. ISSN 0031-9007, 1079-7114. 10.1103/​PhysRevLett.93.130502. URL http:/​/​​abs/​quant-ph/​0404089. arXiv:quant-ph/​0404089.

[41] Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. Synthesis of Quantum Logic Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25 (6): 1000–1010, June 2006. ISSN 0278-0070, 1937-4151. 10.1109/​TCAD.2005.855930. URL http:/​/​​abs/​quant-ph/​0406176. arXiv:quant-ph/​0406176.

[42] Neil J. Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations, June 2016. URL http:/​/​​abs/​1403.2975. arXiv:1403.2975 [quant-ph].

[43] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. Quantum computing enhanced computational catalysis. Physical Review Research, 3 (3), July 2021. ISSN 2643-1564. 10.1103/​PhysRevResearch.3.033055. URL http:/​/​​abs/​2007.14460. arXiv:2007.14460 [physics, physics:quant-ph].

[44] Guang Hao Low. Halving the cost of quantum multiplexed rotations. arXiv:2110.13439 [quant-ph], October 2021. URL http:/​/​​abs/​2110.13439. arXiv: 2110.13439.

[45] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Uniform Spectral Amplification, July 2017. URL http:/​/​​abs/​1707.05391. arXiv:1707.05391 [quant-ph].

[46] Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. arXiv:2002.11649 [physics, physics:quant-ph], July 2021. 10.1103/​PhysRevA.103.042419. URL http:/​/​​abs/​2002.11649. arXiv: 2002.11649.

Cited by

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[2] R. Au-Yeung, B. Camino, O. Rathore, and V. Kendon, "Quantum algorithms for scientific applications", arXiv:2312.14904, (2023).

[3] Dong An, Andrew M. Childs, and Lin Lin, "Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters", arXiv:2312.03916, (2023).

[4] Oscar Watts, Yuta Kikuchi, and Luuk Coopmans, "Quantum Semidefinite Programming with Thermal Pure Quantum States", arXiv:2310.07774, (2023).

[5] Abtin Ameri, Erika Ye, Paola Cappellaro, Hari Krovi, and Nuno F. Loureiro, "Quantum algorithm for the linear Vlasov equation with collisions", Physical Review A 107 6, 062412 (2023).

[6] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yiğit Subaşı, "Efficient quantum linear solver algorithm with detailed running costs", arXiv:2305.11352, (2023).

[7] Diyi Liu, Weijie Du, Lin Lin, James P. Vary, and Chao Yang, "An Efficient Quantum Circuit for Block Encoding a Pairing Hamiltonian", arXiv:2402.11205, (2024).

[8] Quynh T. Nguyen, "The mixed Schur transform: efficient quantum circuit and applications", arXiv:2310.01613, (2023).

[9] Xiao-Ming Zhang and Xiao Yuan, "On circuit complexity of quantum access models for encoding classical data", arXiv:2311.11365, (2023).

[10] Parker Kuklinski and Benjamin Rempfer, "S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for unstructured sparse matrices", arXiv:2401.04234, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-26 10:09:30). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-02-26 10:09:29).