Accelerating Quantum Algorithms With Precomputation

Republished By Plato

Followers: 0

Accelerating Quantum Algorithms with Precomputation PlatoBlockchain Data Intelligence. Vertical Search. Ai.

William J. Huggins and Jarrod R. McClean

Google Quantum AI, Venice, CA, USA

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

Abstract

Real-world applications of computing can be extremely time-sensitive. It would be valuable if we could accelerate such tasks by performing some of the work ahead of time. Motivated by this, we propose a cost model for quantum algorithms that allows quantum precomputation; i.e., for a polynomial amount of “free” computation before the input to an algorithm is fully specified, and methods for taking advantage of it. We analyze two families of unitaries that are asymptotically more efficient to implement in this cost model than in the standard one. The first example of quantum precomputation, based on density matrix exponentiation, could offer an exponential advantage under certain conditions. The second example uses a variant of gate teleportation to achieve a quadratic advantage when compared with implementing the unitaries directly. These examples hint that quantum precomputation may offer a new arena in which to seek quantum advantage.

► BibTeX data

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, title = {Accelerating {Q}uantum {A}lgorithms with {P}recomputation}, author = {Huggins, William J. and McClean, Jarrod R.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1264}, month = feb, year = {2024}<br /> }

► References

[1] S Aaronson. Limitations of quantum advice and one-way communication. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, pages 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https://doi.org/10.1109/ccc.2004.1313854

[2] Scott Aaronson and Andris Ambainis. Forrelation. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, STOC ’15, pages 307–316, New York, NY, USA, 14 June 2015. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https://doi.org/10.1145/2746539.2746547

[3] Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. 18 April 2019. URL http://arxiv.org/abs/1904.08747.
arXiv:1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX quantum, 2 (1): 010103, 29 March 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https://doi.org/10.1103/prxquantum.2.010103

[5] Daniel J Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power of free precomputation. In Advances in Cryptology – ASIACRYPT 2013, Lecture notes in computer science, pages 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/978-3-642-42045-0_17.
https://doi.org/10.1007/978-3-642-42045-0_17

[6] 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. 6 February 2019. URL https://doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, September 2017. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https://doi.org/10.1038/nature23474

[8] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71 (2): 022316, 22 February 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https://doi.org/10.1103/physreva.71.022316

[9] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, July 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https://doi.org/10.1109/tit.2021.3081415

[10] Earl T Campbell and Joe O’Gorman. An efficient magic state approach to small angle rotations. 14 March 2016. URL https://doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, February 2022. 10.1109/focs52979.2021.00063.
https://doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput., 46 (6): 1920–1950, 1 January 2017. ISSN 0097-5397. 10.1137/16M1087072.
https://doi.org/10.1137/16M1087072

[13] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto. Faster quantum chemistry simulation on fault-tolerant quantum computers. New J. Phys., 14 (11): 115023, 27 November 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[14] Pedro C S Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, and Dominic W Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX quantum, 3 (4): 040303, 7 October 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https://doi.org/10.1103/prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang, and Jarrod R McClean. Revisiting dequantization and quantum advantage in learning tasks. 1 December 2021. URL http://arxiv.org/abs/2112.00811.
arXiv:2112.00811

[16] Shawn X Cui, Daniel Gottesman, and Anirudh Krishna. Diagonal gates in the clifford hierarchy. Phys. Rev. A, 95 (1), 26 January 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https://doi.org/10.1103/physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. 14 November 2014. URL http://arxiv.org/abs/1411.4028.
arXiv:1411.4028

[18] Austin G Fowler. Time-optimal quantum computation. 17 October 2012. URL http://arxiv.org/abs/1210.4626.
arXiv:1210.4626

[19] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 19–32, New York, NY, USA, 9 June 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https://doi.org/10.1145/3519935.3519991

[20] Craig Gidney and Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5 (433): 433, 15 April 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney and Austin G Fowler. Flexible layout of surface code computations using AutoCCZ states. 21 May 2019. URL http://arxiv.org/abs/1905.08916.
arXiv:1905.08916

[22] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation. 29 March 2022. URL http://arxiv.org/abs/2203.15993.
arXiv:2203.15993

[23] Daniel Gottesman and Isaac L Chuang. Quantum teleportation is a universal computational primitive. 2 August 1999. URL https://doi.org/10.1038/46503.
https://doi.org/10.1038/46503

[24] Leo Grady and Ali Kemal Sinop. Fast approximate random walker segmentation using eigenvector precomputation. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, June 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https://doi.org/10.1109/cvpr.2008.4587487

[25] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing – STOC ’96, STOC ’96, pages 212–219, New York, New York, USA, 1996. ACM Press. ISBN 9780897917858. 10.1145/237814.237866.
https://doi.org/10.1145/237814.237866

[26] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103 (15): 150502, 9 October 2009. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R McClean. Quantum advantage in learning from experiments. Science, 376 (6598): 1182–1186, 10 June 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https://doi.org/10.1126/science.abn7293

[28] Cody Jones. Distillation protocols for fourier states in quantum computing. 12 March 2013. URL http://arxiv.org/abs/1303.3066.
arXiv:1303.3066

[29] John Kallaugher. A quantum advantage for a natural streaming problem. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 897–908. IEEE, February 2022. 10.1109/focs52979.2021.00091.
https://doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp and Richard J Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the twelfth annual ACM symposium on Theory of computing – STOC ’80, STOC ’80, pages 302–309, New York, New York, USA, 28 April 1980. ACM Press. ISBN 9780897910170. 10.1145/800141.804678.
https://doi.org/10.1145/800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J Yoder. Hamiltonian simulation with optimal sample complexity. Npj Quantum Inf., 3 (1): 1–7, 30 March 2017. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7

[32] François Le Gall. Exponential separation of quantum and classical online space complexity. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA ’06, pages 67–73, New York, NY, USA, 30 July 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https://doi.org/10.1145/1148109.1148119

[33] Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4 (361): 361, 11 November 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum, 3 (205): 205, 2 December 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3 (128): 128, 5 March 2019b. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nat. Phys., 10 (9): 631–633, 27 September 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https://doi.org/10.1038/nphys3029

[37] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX quantum, 2 (4): 040203, 3 December 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https://doi.org/10.1103/prxquantum.2.040203

[38] Iman Marvian and Seth Lloyd. Universal quantum emulator. 8 June 2016. URL http://arxiv.org/abs/1606.02734.
arXiv:1606.02734

[39] F Motzoi, M P Kaicher, and F K Wilhelm. Linear and logarithmic time compositions of quantum many-body operators. Phys. Rev. Lett., 119 (16): 160503, 20 October 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https://doi.org/10.1103/PhysRevLett.119.160503

[40] Michael A Nielsen. Optical quantum computation using cluster states. Phys. Rev. Lett., 93 (4): 040503, 23 July 2004. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.93.040503.
https://doi.org/10.1103/PhysRevLett.93.040503

[41] Bryan O’Gorman, William J Huggins, Eleanor G Rieffel, and K Birgitta Whaley. Generalized swap networks for near-term quantum computing. 13 May 2019. URL http://arxiv.org/abs/1905.05118.
arXiv:1905.05118

[42] Paul Pham and Krysta M Svore. A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth. 27 July 2012. URL http://arxiv.org/abs/1207.6655.
arXiv:1207.6655

[43] R Raussendorf and H J Briegel. A one-way quantum computer. Phys. Rev. Lett., 86 (22): 5188–5191, 28 May 2001. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188

[44] 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, 9 November 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https://doi.org/10.1103/prxquantum.1.020312

[45] Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proc. Math. Phys. Eng. Sci., 465 (2105): 1413–1439, 8 May 2009. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https://doi.org/10.1098/rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz, and John Snyder. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, SIGGRAPH ’02, pages 527–536, New York, NY, USA, 1 July 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https://doi.org/10.1145/566570.566612

[47] James E Smith. A study of branch prediction strategies. In 25 years of the international symposia on Computer architecture (selected papers), ISCA ’98, pages 202–215, New York, NY, USA, 1 August 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https://doi.org/10.1145/285930.285980

[48] Rolando D Somma and Yiğit Subaşı. Complexity of quantum state verification in the quantum linear systems problem. PRX quantum, 2 (1): 010315, 27 January 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https://doi.org/10.1103/prxquantum.2.010315

[49] Barbara M Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87 (2): 307–346, 7 April 2015. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https://doi.org/10.1103/revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung, and Isaac L Chuang. Methodology for quantum logic gate construction. Phys. Rev. A, 62 (5), 18 October 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https://doi.org/10.1103/physreva.62.052316

Cited by

[1] Dar Gilboa and Jarrod R. McClean, “Exponential Quantum Communication Advantage in Distributed Learning”, arXiv:2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost, and Mikel Sanz, “Quantum approximated cloning-assisted density matrix exponentiation”, arXiv:2311.11751, (2023).

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

Could not fetch Crossref cited-by data during last attempt 2024-02-22 13:13:06: Could not fetch cited-by data for 10.22331/q-2024-02-22-1264 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-02-22-1264/

Time Stamp: February 22, 2024

More from Quantum Journal

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Quantum Journal

Source Node: 1838608

Time Stamp: May 22, 2023

Partitioning qubits in hypergraph product codes to implement logical gates

Source Cluster:

Quantum Journal

Source Node: 1905467

Time Stamp: Oct 24, 2023

Accelerating Quantum Algorithms with Precomputation

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Randomizing multi-product formulas for Hamiltonian simulation

Testing symmetry on quantum computers

Quantum circuit compilation and hybrid computation using Pauli-based computation

A no-go theorem on the nature of the gravitational field beyond quantum theory

Design of quantum optical experiments with logic artificial intelligence

Quantum circuit debugging and sensitivity analysis via local inversions

Quantum circuits for toric code and X-cube fracton model

Clifford Circuits can be Properly PAC Learned if and only if $textsf{RP}=textsf{NP}$

A Pair Measurement Surface Code on Pentagons

Partitioning qubits in hypergraph product codes to implement logical gates

About Us

Vertical Search & Ai

Platform

Stay Connected

Account