Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm

Jessica Lemieux; Bettina Heim; David Poulin; Krysta Svore; Matthias Troyer

doi:10.22331/q-2020-06-29-287

Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm

Jessica Lemieux¹, Bettina Heim², David Poulin^1,3, Krysta Svore², and Matthias Troyer²

¹Département de Physique & Institut Quantique, Université de Sherbrooke, Québec, Canada
²Quantum Architecture and Computation Group, Microsoft Research, Redmond, WA 98052, USA
³Canadian Institute for Advanced Research, Toronto, Ontario, Canada M5G 1Z8

Published:	2020-06-29, volume 4, page 287
Eprint:	arXiv:1910.01659v2
Doi:	https://doi.org/10.22331/q-2020-06-29-287
Citation:	Quantum 4, 287 (2020).

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

Abstract

We present a detailed circuit implementation of Szegedy's quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.

► BibTeX data

@article{Lemieux2020efficientquantum,
  doi = {10.22331/q-2020-06-29-287},
  url = {https://doi.org/10.22331/q-2020-06-29-287},
  title = {Efficient {Q}uantum {W}alk {C}ircuits for {M}etropolis-{H}astings {A}lgorithm},
  author = {Lemieux, Jessica and Heim, Bettina and Poulin, David and Svore, Krysta and Troyer, Matthias},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {287},
  month = jun,
  year = {2020}
}

► References

[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03, page 20, New York, New York, USA, 2003. ACM Press. ISBN 1581136749. 10.1145/780542.780546.
https://doi.org/10.1145/780542.780546

[2] Andris Ambainis. Quantum walk algorithm for element distinctness. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 22–31, 2004. 10.1109/focs.2004.54.
https://doi.org/10.1109/focs.2004.54

[3] Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15: 3241–3253, 1982. 10.1088/0305-4470/15/10/028.
https://doi.org/10.1088/0305-4470/15/10/028

[4] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52 (5): 3457–3467, nov 1995. ISSN 10502947. 10.1103/PhysRevA.52.3457.
https://doi.org/10.1103/PhysRevA.52.3457

[5] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A - Atomic, Molecular, and Optical Physics, 91 (5): 052317, may 2015. ISSN 10941622. 10.1103/PhysRevA.91.052317.
https://doi.org/10.1103/PhysRevA.91.052317

[6] S. Boixo, E. Knill, and R. D. Somma. Fast quantum algorithms for traversing paths of eigenstates. may 2010. URL https://arxiv.org/abs/1005.3034.
arXiv:1005.3034

[7] Sergio Boixo, Emanuel Knill, and Rolando Somma. Eigenpath traversal by phase randomization. Quantum Information and Computation, 9 (9&10): 0833, 2009. URL http://arxiv.org/abs/0903.1652.
arXiv:0903.1652

[8] 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 Journal of Physics, 14 (11): 115023, nov 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum Computation by Adiabatic Evolution. jan 2000. URL http://arxiv.org/abs/quant-ph/0001106.
arXiv:quant-ph/0001106

[10] Roy J. Glauber. Time-dependent statistics of the Ising model. Journal of Mathematical Physics, 4 (2): 294–307, feb 1963. ISSN 00222488. 10.1063/1.1703954.
https://doi.org/10.1063/1.1703954

[11] Jeongwan Haah. Product Decomposition of Periodic Functions in Quantum Signal Processing. jun 2018. 10.22331/q-2019-10-07-190.
https://doi.org/10.22331/q-2019-10-07-190

[12] W K Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57 (1): 97–109, apr 1970. ISSN 0006-3444. 10.1093/biomet/57.1.97.
https://doi.org/10.1093/biomet/57.1.97

[13] Janus Collaboration, F. Belletti, M. Cotallo, A. Cruz, L. A. Fernández, A. Gordillo, M. Guidetti, A. Maiorano, F. Mantovani, E. Marinari, V. Martín-Mayor, A. Muñoz-Sudupe, D. Navarro, G. Parisi, S. Pérez-Gaviro, M. Rossi, J. J. Ruiz-Lorenzo, S. F. Schifano, D. Sciretti, A. Tarancón, R. Tripiccione, and J. L. Velasco. JANUS: an FPGA-based System for High Performance Scientific Computing. Computing in Science & Engineering, 11 (1): 48–58, 2009. 10.1109/MCSE.2009.11.
https://doi.org/10.1109/MCSE.2009.11

[14] Janus Collaboration, M. Baity-Jesi, R. A. Banos, A. Cruz, L. A. Fernandez, J. M. Gil-Narvion, A. Gordillo-Guerrero, M. Guidetti, D. Iniguez, A. Maiorano, F. Mantovani, E. Marinari, V. Martin-Mayor, J. Monforte-Garcia, A. Munoz Sudupe, D. Navarro, G. Parisi, M. Pivanti, S. Perez-Gaviro, F. Ricci-Tersenghi, J. J. Ruiz-Lorenzo, S. F. Schifano, B. Seoane, A. Tarancon, P. Tellez, R. Tripiccione, and D. Yllanes. Reconfigurable computing for Monte Carlo simulations: results and prospects of the Janus project. The European Physical Journal Special Topics, 210 (33), 2012. 10.1140/epjst/e2012-01636-9.
https://doi.org/10.1140/epjst/e2012-01636-9

[15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598): 671–680, 1983. ISSN 00368075. 10.1126/science.220.4598.671.
https://doi.org/10.1126/science.220.4598.671

[16] A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. nov 1995. URL http://arxiv.org/abs/quant-ph/9511026.
arXiv:quant-ph/9511026

[17] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin. Resource estimate for quantum many-body ground state preparation on a quantum computer. 2020. URL https://arxiv.org/abs/2006.04650.
arXiv:2006.04650

[18] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. oct 2016. 10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163

[19] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Physical Review Letters, 118 (1): 010501, jan 2017. ISSN 10797114. 10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501

[20] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6 (4): 041067, dec 2016. ISSN 21603308. 10.1103/PhysRevX.6.041067.
https://doi.org/10.1103/PhysRevX.6.041067

[21] F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40: 142–164. 10.1137/090745854.
https://doi.org/10.1137/090745854

[22] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. In Computational Complexity, volume 14, pages 122–152. Springer, jun 2005. 10.1007/s00037-005-0194-x.
https://doi.org/10.1007/s00037-005-0194-x

[23] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21 (6): 1087–1092, jun 1953. ISSN 00219606. 10.1063/1.1699114.
https://doi.org/10.1063/1.1699114

[24] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, jul 2014. ISSN 10959203. 10.1126/science.1252319.
https://doi.org/10.1126/science.1252319

[25] Neil J Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Information and Computation, 16 (11&12): 0901, 2016. URL http://arxiv.org/abs/1403.2975.
arXiv:1403.2975

[26] Terry Rudolph and Lov Grover. A 2 rebit gate universal for quantum computing. oct 2002. URL https://arxiv.org/abs/quant-ph/0210187.
arXiv:quant-ph/0210187

[27] R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Physical Review Letters, 101 (13): 130504, sep 2008. ISSN 00319007. 10.1103/PhysRevLett.101.130504.
https://doi.org/10.1103/PhysRevLett.101.130504

[28] Mario Szegedy. Quantum speed-up of Markov Chain based algorithms. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 32–41, 2004. 10.1109/focs.2004.53.
https://doi.org/10.1109/focs.2004.53

[29] K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. Quantum Metropolis sampling. Nature, 471 (7336): 87–90, mar 2011. ISSN 00280836. 10.1038/nature09770.
https://doi.org/10.1038/nature09770

[30] Marija Vucelja. Lifting—A nonreversible Markov chain Monte Carlo algorithm. American Journal of Physics, 84 (12): 958–968, dec 2016. ISSN 0002-9505. 10.1119/1.4961596.
https://doi.org/10.1119/1.4961596

[31] Man-Hong Yung and Alán Aspuru-Guzik. A quantum-quantum Metropolis algorithm. Proceedings of the National Academy of Sciences of the United States of America, 109 (3): 754–9, jan 2012. ISSN 1091-6490. 10.1073/pnas.1111758109.
https://doi.org/10.1073/pnas.1111758109

Cited by

[1] Guglielmo Mazzola, "Quantum computing for chemistry and physics applications from a Monte Carlo perspective", The Journal of Chemical Physics 160 1, 010901 (2024).

[2] Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 1131 (2023) ISBN:9781450399135.

[3] Naeimeh Mohseni, Peter L. McMahon, and Tim Byrnes, "Ising machines as hardware solvers of combinatorial optimization problems", Nature Reviews Physics 4 6, 363 (2022).

[4] Scott E. Smart and David A. Mazziotti, "Many-fermion simulation from the contracted quantum eigensolver without fermionic encoding of the wave function", Physical Review A 105 6, 062424 (2022).

[5] Haibo Huang, Wu Zhao, Xiaofan Zhang, and Xinlong Wu, "Quantum Semi-trust Evaluation Model with Graph-based Quantum Walk Teleportation", International Journal of Theoretical Physics 61 6, 178 (2022).

[6] Hongbin Liu, Guang Hao Low, Damian S. Steiger, Thomas Häner, Markus Reiher, and Matthias Troyer, "Prospects of quantum computing for molecular sciences", Materials Theory 6 1, 11 (2022).

[7] Thomas E. Baker and David Poulin, "Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer", Physical Review Research 2 4, 043238 (2020).

[8] Gösta Gustafson, Stefan Prestel, Michael Spannowsky, and Simon Williams, "Collider events on a quantum computer", Journal of High Energy Physics 2022 11, 35 (2022).

[9] Guglielmo Mazzola, "Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers", Physical Review A 104 2, 022431 (2021).

[10] Sergio A. Ortega and Miguel A. Martin‐Delgado, "SQUWALS: A Szegedy QUantum WALks Simulator", Advanced Quantum Technologies 2400022 (2024).

[11] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin, "Resource estimate for quantum many-body ground-state preparation on a quantum computer", Physical Review A 103 5, 052408 (2021).

[12] Sergio A. Ortega and Miguel A. Martin-Delgado, "Discrete-time semiclassical Szegedy quantum walks", Physica A: Statistical Mechanics and its Applications 625, 129021 (2023).

[13] Roberto Campos, P. A. M. Casares, and M. A. Martin-Delgado, "Quantum Metropolis Solver: a quantum walks approach to optimization problems", Quantum Machine Intelligence 5 2, 28 (2023).

[14] Gabriel Escrig, Roberto Campos, Pablo A M Casares, and M A Martin-Delgado, "Parameter estimation of gravitational waves with a quantum metropolis algorithm", Classical and Quantum Gravity 40 4, 045001 (2023).

[15] Karuna Kadian, Sunita Garhwal, and Ajay Kumar, "Quantum walk and its application domains: A systematic review", Computer Science Review 41, 100419 (2021).

[16] Mudassir Moosa, Thomas W Watts, Yiyou Chen, Abhijat Sarma, and Peter L McMahon, "Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions", Quantum Science and Technology 9 1, 015002 (2024).

[17] David Layden, Guglielmo Mazzola, Ryan V. Mishmash, Mario Motta, Pawel Wocjan, Jin-Sung Kim, and Sarah Sheldon, "Quantum-enhanced Markov chain Monte Carlo", Nature 619 7969, 282 (2023).

[18] Zoltán Udvarnoki, Gábor Fáth, and Norbert Fogarasi, "Quantum advantage of Monte Carlo option pricing", Journal of Physics Communications 7 5, 055001 (2023).

[19] Andrew J. Holbrook, "A Quantum Parallel Markov Chain Monte Carlo", Journal of Computational and Graphical Statistics 32 4, 1402 (2023).

[20] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

[21] Koichi Miyamoto, "Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration", Physical Review Research 5 3, 033059 (2023).

[22] Jonathan Allcock, Anna Vangone, Agnes Meyder, Stanislaw Adaszewski, Martin Strahm, Chang-Yu Hsieh, and Shengyu Zhang, "The Prospects of Monte Carlo Antibody Loop Modelling on a Fault-Tolerant Quantum Computer", Frontiers in Drug Discovery 2, 908870 (2022).

[23] Taylor L Patti, Omar Shehab, Khadijeh Najafi, and Susanne F Yelin, "Markov chain Monte Carlo enhanced variational quantum algorithms", Quantum Science and Technology 8 1, 015019 (2023).

[24] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[25] 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 (2020).

[26] Khadeejah Bepari, Sarah Malik, Michael Spannowsky, and Simon Williams, "Quantum walk approach to simulating parton showers", Physical Review D 106 5, 056002 (2022).

[27] Thais L. Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", Scientific Reports 13 1, 18258 (2023).

[28] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices", SIAM Journal on Matrix Analysis and Applications 45 1, 801 (2024).

[29] 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 (2021).

[30] P A M Casares, Roberto Campos, and M A Martin-Delgado, "QFold: quantum walks and deep learning to solve protein folding", Quantum Science and Technology 7 2, 025013 (2022).

[31] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices", arXiv:2203.10236, (2022).

[32] Garrett T. Floyd, David P. Landau, and Michael R. Geller, "Quantum algorithm for Wang-Landau sampling", arXiv:2208.09543, (2022).

[33] Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G. S. L. Brandão, "Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end", arXiv:2212.01513, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-16 14:39:06) and SAO/NASA ADS (last updated successfully 2024-05-16 14:39:07). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.