Analysis and limitations of modified circuit-to-Hamiltonian constructions
1DAMTP, CQIF, University of Cambridge
2IQIM, California Institute of Technology
| Published: | 2018-09-19, volume 2, page 94 |
| Eprint: | arXiv:1609.08571v3 |
| Doi: | https://doi.org/10.22331/q-2018-09-19-94 |
| Citation: | Quantum 2, 94 (2018). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the $\Omega(T^{-2})$ scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.
Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight $O(T^{-2})$ upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the $\Omega(T^{-3})$ scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the $O(T^{-2})$ bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.
► BibTeX data
► References
[1] Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi, ``Classical and quantum computing'' Springer New York (2002).
https://doi.org/10.1007/978-0-387-36944-0_13
[2] Julia Kempe, Alexei Kitaev, and Oded Regev, ``The Complexity of the Local Hamiltonian Problem'' SIAM Journal on Computing 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226
[3] Roberto Oliveiraand Barbara M. Terhal ``The complexity of quantum spin systems on a two-dimensional square lattice'' Quantum Information & Computation 1–23 (2005).
[4] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, ``Adiabatic quantum computation is equivalent to standard quantum computation'' SIAM review 50, 755–787 (2008).
https://doi.org/10.1137/080734479
[5] Jacob Biamonteand Peter Love ``Realizable Hamiltonians for universal adiabatic quantum computers'' Physical Review A 78, 012352 (2008).
https://doi.org/10.1103/PhysRevA.78.012352
arXiv:1311.3161
[6] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe, ``The power of quantum systems on a line'' Communications in Mathematical Physics 287, 41–65 (2009).
https://doi.org/10.1007/s00220-008-0710-3
arXiv:0705.4077
[7] Toby Cubittand Ashley Montanaro ``Complexity classification of local Hamiltonian problems'' SIAM Journal on Computing 45, 268–316 (2016).
https://doi.org/10.1137/140998287
arXiv:0704.1287
[8] Dorit Aharonov, Itai Arad, and Thomas Vidick, ``Guest column: the quantum PCP conjecture'' Acm SIGACT news 44, 47–79 (2013).
https://doi.org/10.1145/2491533.2491549
[9] Richard P. Feynman ``Quantum Mechanical Computers'' Optics News 11, 11 (1985).
https://doi.org/10.1364/ON.11.2.000011
https://www.osapublishing.org/abstract.cfm?URI=on-11-2-11
[10] David Gossetand Daniel Nagaj ``Quantum 3-SAT Is QMA1-Complete'' 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 756–765 (2013).
https://doi.org/10.1109/FOCS.2013.86
[11] Daniel Gottesmanand Sandy Irani ``The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems'' Theory of Computing 9, 31–116 (2013).
https://doi.org/10.4086/toc.2013.v009a002
arXiv:0905.2419
[12] Nikolas P. Breuckmannand Barbara M. Terhal ``Space-time circuit-to-Hamiltonian construction and its applications'' Journal of Physics A: Mathematical and Theoretical 47, 195304 (2014).
https://doi.org/10.1088/1751-8113/47/19/195304
arXiv:1311.6101
[13] Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami, ``The Local Hamiltonian problem on a line with eight states is QMA-complete'' Quantum Information and Computation 13, 28 (2013).
arXiv:1312.1469
[14] Daniel Nagaj ``Tick-tock Goes the Clock'' (2014).
https://www.youtube.com/watch?v=ADPzjtt6V04
[15] Johannes Bausch, Toby Cubitt, and Maris Ozols, ``The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension'' Annales Henri Poincaré 52 (2017).
https://doi.org/10.1007/s00023-017-0609-7
arXiv:1605.01718
[16] Naïri Usher, Matty J. Hoban, and Dan E. Browne, ``Nonunitary quantum computation in the ground space of local Hamiltonians'' Physical Review A 96, 032321 (2017).
https://doi.org/10.1103/PhysRevA.96.032321
arXiv:1703.08118
[17] Libor Caha, Zeph Landau, and Daniel Nagaj, ``The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning'' (2017).
https://doi.org/10.1103/PhysRevA.97.062306
arXiv:1712.07395
[18] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani, ``The detectability lemma and quantum gap amplification'' Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09 417 (2009).
https://doi.org/10.1145/1536414.1536472
http://portal.acm.org/citation.cfm?doid=1536414.1536472
[19] Johannes Bausch ``Quantum Stochastic Processes and Quantum Many-Body Physics'' thesis (2017).
https://doi.org/10.17863/CAM.16755
[20] Jonathan Kelner ``18.409, Topics in Theoretical Computer Science: An Algorithmist's Toolkit'' Fall 2009, Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu.
https://ocw.mit.edu.
[21] Asher Peres ``Reversible logic and quantum computers'' Physical Review A 32, 3266–3276 (1985).
https://doi.org/10.1103/PhysRevA.32.3266
[22] Anand Gantiand Rolando Somma ``On the gap of Hamiltonians for the adiabatic simulation of quantum circuits'' International Journal of Quantum Information 11, 1350063 (2013).
https://doi.org/10.1142/S0219749913500639
arXiv:1307.4993
[23] Toby Cubitt ``Lecture notes in Advanced Quantum Information Theory'' (2015).
[24] David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer, ``Markov chains and mixing times'' American Mathematical Soc. (2009).
[25] J. Cheeger ``A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis'' Princeton Univ. Press, Princeton, N. J. (1970).
[26] Alistair Sinclairand Mark Jerrum ``Approximate counting, uniform generation and rapidly mixing Markov chains'' Information and Computation 82, 93–133 (1989).
https://doi.org/10.1016/0890-5401(89)90067-9
[27] Dorit Aharonovand Tomer Naveh ``Quantum NP-a survey'' (2002).
[28] Tameem Albashand Daniel A. Lidar ``Adiabatic quantum computation'' Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
arXiv:1611.04471
[29] Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, and Peter Shor, ``Unstructured Randomness, Small Gaps and Localization'' Quantum Information & Computation 11 (2011).
arXiv:1010.0009
[30] Camille Jordan ``Essai sur la géométrie à n dimensions'' Bulletin de la Société mathématique de France 3, 103–174 (1875).
https://eudml.org/doc/85325
[31] Sergey Bravyi, Arvid Bessen, and Barbara Terhal, ``Merlin-Arthur games and stoquastic complexity'' (2006).
[32] Sergey Bravyiand Barbara Terhal ``Complexity of stoquastic frustration-free Hamiltonians'' Siam journal on computing 39, 1462–1485 (2009).
https://doi.org/10.1137/08072689X
arXiv:0806.1746
[33] Guan-Yu Chenand Laurent Saloff-Coste ``On the mixing time and spectral gap for birth and death chains'' ALEA Lat. Am. J. Probab. Math. Stat. 10, 293–321 (2013).
arXiv:1304.4346
[1] Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi, ``Classical and quantum computing'' Springer New York (2002).
https://doi.org/10.1007/978-0-387-36944-0_13
[2] Julia Kempe, Alexei Kitaev, and Oded Regev, ``The Complexity of the Local Hamiltonian Problem'' SIAM Journal on Computing 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226
[3] Roberto Oliveiraand Barbara M. Terhal ``The complexity of quantum spin systems on a two-dimensional square lattice'' Quantum Information & Computation 1–23 (2005).
[4] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, ``Adiabatic quantum computation is equivalent to standard quantum computation'' SIAM review 50, 755–787 (2008).
https://doi.org/10.1137/080734479
[5] Jacob Biamonteand Peter Love ``Realizable Hamiltonians for universal adiabatic quantum computers'' Physical Review A 78, 012352 (2008).
https://doi.org/10.1103/PhysRevA.78.012352
arXiv:1311.3161
[6] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe, ``The power of quantum systems on a line'' Communications in Mathematical Physics 287, 41–65 (2009).
https://doi.org/10.1007/s00220-008-0710-3
arXiv:0705.4077
[7] Toby Cubittand Ashley Montanaro ``Complexity classification of local Hamiltonian problems'' SIAM Journal on Computing 45, 268–316 (2016).
https://doi.org/10.1137/140998287
arXiv:0704.1287
[8] Dorit Aharonov, Itai Arad, and Thomas Vidick, ``Guest column: the quantum PCP conjecture'' Acm SIGACT news 44, 47–79 (2013).
https://doi.org/10.1145/2491533.2491549
[9] Richard P. Feynman ``Quantum Mechanical Computers'' Optics News 11, 11 (1985).
https://doi.org/10.1364/ON.11.2.000011
https://www.osapublishing.org/abstract.cfm?URI=on-11-2-11
[10] David Gossetand Daniel Nagaj ``Quantum 3-SAT Is QMA1-Complete'' 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 756–765 (2013).
https://doi.org/10.1109/FOCS.2013.86
[11] Daniel Gottesmanand Sandy Irani ``The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems'' Theory of Computing 9, 31–116 (2013).
https://doi.org/10.4086/toc.2013.v009a002
arXiv:0905.2419
[12] Nikolas P. Breuckmannand Barbara M. Terhal ``Space-time circuit-to-Hamiltonian construction and its applications'' Journal of Physics A: Mathematical and Theoretical 47, 195304 (2014).
https://doi.org/10.1088/1751-8113/47/19/195304
arXiv:1311.6101
[13] Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami, ``The Local Hamiltonian problem on a line with eight states is QMA-complete'' Quantum Information and Computation 13, 28 (2013).
arXiv:1312.1469
[14] Daniel Nagaj ``Tick-tock Goes the Clock'' (2014).
https://www.youtube.com/watch?v=ADPzjtt6V04
[15] Johannes Bausch, Toby Cubitt, and Maris Ozols, ``The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension'' Annales Henri Poincaré 52 (2017).
https://doi.org/10.1007/s00023-017-0609-7
arXiv:1605.01718
[16] Naïri Usher, Matty J. Hoban, and Dan E. Browne, ``Nonunitary quantum computation in the ground space of local Hamiltonians'' Physical Review A 96, 032321 (2017).
https://doi.org/10.1103/PhysRevA.96.032321
arXiv:1703.08118
[17] Libor Caha, Zeph Landau, and Daniel Nagaj, ``The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning'' (2017).
https://doi.org/10.1103/PhysRevA.97.062306
arXiv:1712.07395
[18] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani, ``The detectability lemma and quantum gap amplification'' Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09 417 (2009).
https://doi.org/10.1145/1536414.1536472
http://portal.acm.org/citation.cfm?doid=1536414.1536472
[19] Johannes Bausch ``Quantum Stochastic Processes and Quantum Many-Body Physics'' thesis (2017).
https://doi.org/10.17863/CAM.16755
[20] Jonathan Kelner ``18.409, Topics in Theoretical Computer Science: An Algorithmist's Toolkit'' Fall 2009, Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu.
https://ocw.mit.edu.
[21] Asher Peres ``Reversible logic and quantum computers'' Physical Review A 32, 3266–3276 (1985).
https://doi.org/10.1103/PhysRevA.32.3266
[22] Anand Gantiand Rolando Somma ``On the gap of Hamiltonians for the adiabatic simulation of quantum circuits'' International Journal of Quantum Information 11, 1350063 (2013).
https://doi.org/10.1142/S0219749913500639
arXiv:1307.4993
[23] Toby Cubitt ``Lecture notes in Advanced Quantum Information Theory'' (2015).
[24] David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer, ``Markov chains and mixing times'' American Mathematical Soc. (2009).
[25] J. Cheeger ``A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis'' Princeton Univ. Press, Princeton, N. J. (1970).
[26] Alistair Sinclairand Mark Jerrum ``Approximate counting, uniform generation and rapidly mixing Markov chains'' Information and Computation 82, 93–133 (1989).
https://doi.org/10.1016/0890-5401(89)90067-9
[27] Dorit Aharonovand Tomer Naveh ``Quantum NP-a survey'' (2002).
[28] Tameem Albashand Daniel A. Lidar ``Adiabatic quantum computation'' Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
arXiv:1611.04471
[29] Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, and Peter Shor, ``Unstructured Randomness, Small Gaps and Localization'' Quantum Information & Computation 11 (2011).
arXiv:1010.0009
[30] Camille Jordan ``Essai sur la géométrie à n dimensions'' Bulletin de la Société mathématique de France 3, 103–174 (1875).
https://eudml.org/doc/85325
[31] Sergey Bravyi, Arvid Bessen, and Barbara Terhal, ``Merlin-Arthur games and stoquastic complexity'' (2006).
[32] Sergey Bravyiand Barbara Terhal ``Complexity of stoquastic frustration-free Hamiltonians'' Siam journal on computing 39, 1462–1485 (2009).
https://doi.org/10.1137/08072689X
arXiv:0806.1746
[33] Guan-Yu Chenand Laurent Saloff-Coste ``On the mixing time and spectral gap for birth and death chains'' ALEA Lat. Am. J. Probab. Math. Stat. 10, 293–321 (2013).
arXiv:1304.4346
Cited by
[1] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt, "Translationally Invariant Universal Quantum Hamiltonians in 1D", Annales Henri Poincaré 23 1, 223 (2022).
[2] Alexandru Gheorghiu and Thomas Vidick, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) 1024 (2019) ISBN:978-1-7281-4952-3.
[3] Davide Orsucci and Vedran Dunjko, "On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number", Quantum 5, 573 (2021).
[4] Sevag Gharibian and Justin Yirka, "The complexity of simulating local measurements on quantum systems", Quantum 3, 189 (2019).
[5] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman, "Importance of the Spectral gap in Estimating Ground-State Energies", PRX Quantum 3 4, 040327 (2022).
[6] Joel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, and Barbara M. Terhal, "Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians", SIAM Journal on Computing 49 6, 1332 (2020).
[7] Johannes Bausch, Toby S. Cubitt, Angelo Lucia, and David Perez-Garcia, "Undecidability of the Spectral Gap in One Dimension", Physical Review X 10 3, 031038 (2020).
[8] Jie Sun and Songfeng Lu, "On the quantum adiabatic evolution with the most general system Hamiltonian", Quantum Information Processing 18 7, 211 (2019).
[9] R. J. Costales, A. Gunning, and T. Dorlas, "Efficiency of Feynman's quantum computer", Physical Review A 111 2, 022615 (2025).
[10] Johannes Bausch, Toby S. Cubitt, and James D. Watson, "Uncomputability of phase diagrams", Nature Communications 12 1, 452 (2021).
[11] Stefano Barison, Filippo Vicentini, Ignacio Cirac, and Giuseppe Carleo, "Variational dynamics as a ground-state problem on a quantum computer", Physical Review Research 4 4, 043161 (2022).
[12] Florian Meier, Marcus Huber, Paul Erker, and Jake Xuereb, "Autonomous quantum processing unit: an autonomous thermal computing machine & its physical limitations", Reports on Progress in Physics 89 7, 077601 (2026).
[13] Johannes Bausch, "Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction", Annales Henri Poincaré 21 1, 81 (2020).
[14] Sevag Gharibian, "Guest Column: The 7 faces of quantum NP", ACM SIGACT News 54 4, 54 (2023).
[15] Anne Broadbent and Alex B. Grilo, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) 196 (2020) ISBN:978-1-7281-9621-3.
[16] Hugo Delavenne, François Le Gall, Yupan Liu, and Masayuki Miyamoto, "Quantum Merlin-Arthur proof systems for synthesizing quantum states", Quantum 9, 1688 (2025).
[17] Anne Broadbent and Alex Bredariol Grilo, "QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge", SIAM Journal on Computing 51 4, 1400 (2022).
[18] Shane Dooley, Graham Kells, Hosho Katsura, and Tony C. Dorlas, "Simulating quantum circuits by adiabatic computation: Improved spectral gap bounds", Physical Review A 101 4, 042302 (2020).
[19] Johannes Bausch, Toby Cubitt, and Maris Ozols, "The Complexity of Translationally Invariant Spin Chains with Low Local Dimension", Annales Henri Poincaré 18 11, 3449 (2017).
[20] Johannes Bausch and Stephen Piddock, "The complexity of translationally invariant low-dimensional spin lattices in 3D", Journal of Mathematical Physics 58 11, 111901 (2017).
[21] Johannes Bausch, Toby Cubitt, Angelo Lucia, and David Perez-Garcia, "Undecidability of the Spectral Gap in One Dimension", arXiv:1810.01858, (2018).
[22] Libor Caha, Zeph Landau, and Daniel Nagaj, "Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning", Physical Review A 97 6, 062306 (2018).
[23] Elizabeth Crosson and John Bowen, "Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians", arXiv:1703.10133, (2017).
[24] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi, "Verification of quantum computation: An overview of existing approaches", arXiv:1709.06984, (2017).
[25] Burhan Gulbahar, "Quantum path computing: computing architecture with propagation paths in multiple plane diffraction of classical sources of fermion and boson particles", Quantum Information Processing 18 6, 167 (2019).
[26] James D. Watson, Johannes Bausch, and Sevag Gharibian, "The Complexity of Translationally Invariant Problems beyond Ground State Energies", arXiv:2012.12717, (2020).
[27] Sevag Gharibian, "The 7 faces of quantum NP", arXiv:2310.18010, (2023).
[28] Johannes Bausch, "Classifying Data with Local Hamiltonians", arXiv:1807.00804, (2018).
[29] Johannes Bausch, "Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction", arXiv:1810.00865, (2018).
[30] Johannes Bausch, "Classifying data using near-term quantum devices", International Journal of Quantum Information 16 8, 1840001-0924 (2018).
[31] Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani, Hamid Reza Naeij, Ulysse Chabaud, Sevag Gharibian, and Saeed Mehraban, "Energy, Bosons and Computational Complexity", arXiv:2510.08545, (2025).
[32] James D. Watson, "Detailed Analysis of Circuit-to-Hamiltonian Mappings", arXiv:1910.01481, (2019).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 23:04:22) and SAO/NASA ADS (last updated successfully 2026-08-09 23:04:27). 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.