Analysis and limitations of modified circuit-to-Hamiltonian constructions

Johannes Bausch1 and Elizabeth Crosson2

1DAMTP, CQIF, University of Cambridge
2IQIM, California Institute of Technology

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] A. Y. Kitaev, A. Shen, and M. N. Vyalyi, ``Classical and quantum computing'' Springer New York (2002).
https://doi.org/10.1007/978-0-387-36944-0_13

[2] J. Kempe, A. Kitaev, and O. Regev, ``The Complexity of the Local H'' SIAM Journal on Computing 35, 1070-1097 (2006).
https://doi.org/10.1137/S0097539704445226
arXiv:quant-ph/0406180

[3] R. Oliveiraand B. M. Terhal ``The complexity of quantum spin systems on a two-dimensional square lattice'' Quantum Information & 1-23 (2005).
arXiv:quant-ph/0504050

[4] D. Aharonov, W. Van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, ``Adiabatic quantum computation is equivalent to standard quantum computation'' SIAM review 50, 755-787 (2008).
https://doi.org/10.1137/080734479
arXiv:quant-ph/0405098

[5] J. Biamonteand P. Love ``Realizable H'' Physical Review A 78, 012352 (2008).
https://doi.org/10.1103/PhysRevA.78.012352
arXiv:1311.3161

[6] D. Aharonov, D. Gottesman, S. Irani, and J. 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] T. Cubittand A. Montanaro ``Complexity classification of local H'' SIAM Journal on Computing 45, 268-316 (2016).
https://doi.org/10.1137/140998287
arXiv:0704.1287

[8] D. Aharonov, I. Arad, and T. Vidick, ``Guest column: the quantum PCP'' Acm SIGACT news 44, 47-79 (2013).
https://doi.org/10.1145/2491533.2491549

[9] R. P. Feynman ``Quantum Mechanical Computers'' Optics News 11, 11 (1985).
https://doi.org/10.1364/ON.11.2.000011

[10] D. Gossetand D. 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] D. Gottesmanand S. 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] N. P. Breuckmannand B. 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] S. Hallgren, D. Nagaj, and S. Narayanaswami, ``The Local H'' Quantum Information and Computation 13, 28 (2013).
arXiv:1312.1469

[14] D. Nagaj ``Tick-tock G'' (2014).
https:/​/​www.youtube.com/​watch?v=ADPzjtt6V04

[15] J. Bausch, T. Cubitt, and M. 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] N. Usher, M. J. Hoban, and D. 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] L. Caha, Z. Landau, and D. 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] D. Aharonov, I. Arad, Z. Landau, and U. 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

[19] J. Bausch ``Quantum Stochastic Processes and Quantum Many-Body Physics'' thesis (2017).
https://doi.org/10.17863/CAM.16755

[20] J. Kelner ``18.409, Topics in Theoretical Computer Science: An Algorithmist's Toolkit''.

[21] A. Peres ``Reversible logic and quantum computers'' Physical Review A 32, 3266-3276 (1985).
https://doi.org/10.1103/PhysRevA.32.3266

[22] A. Gantiand R. Somma ``On the gap of H'' International Journal of Quantum Information 11, 1350063 (2013).
https://doi.org/10.1142/S0219749913500639
arXiv:1307.4993

[23] T. Cubitt ``Lecture notes in A'' (2015).

[24] D. A. Levin, Y. Peres, and E. L. Wilmer, ``Markov chains and mixing times'' American Mathematical Soc. (2009).

[25] J. Cheeger ``A lower bound for the smallest eigenvalue of the L'' Princeton Univ. Press, Princeton, N. J. (1970).

[26] A. Sinclairand M. Jerrum ``Approximate counting, uniform generation and rapidly mixing M'' Information and Computation 82, 93-133 (1989).
https://doi.org/10.1016/0890-5401(89)90067-9

[27] D. Aharonovand T. Naveh ``Quantum NP'' (2002).
arXiv:quant-ph/0210077

[28] T. Albashand D. A. Lidar ``Adiabatic quantum computation'' Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
arXiv:1611.04471

[29] E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, and P. Shor, ``Unstructured Randomness, Small Gaps and Localization'' Quantum Information & 11 (2011).
arXiv:1010.0009

[30] C. 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] S. Bravyi, A. Bessen, and B. Terhal, ``Merlin-A'' (2006).
arXiv:quant-ph/0611021

[32] S. Bravyiand B. Terhal ``Complexity of stoquastic frustration-free H'' Siam journal on computing 39, 1462-1485 (2009).
https://doi.org/10.1137/08072689X
arXiv:0806.1746

[33] G.-Y. Chenand L. 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
http:/​/​arxiv.org/​abs/​1304.4346

[1] A. Y. Kitaev, A. Shen, and M. N. Vyalyi, ``Classical and quantum computing'' Springer New York (2002).
https://doi.org/10.1007/978-0-387-36944-0_13

[2] J. Kempe, A. Kitaev, and O. Regev, ``The Complexity of the Local H'' SIAM Journal on Computing 35, 1070-1097 (2006).
https://doi.org/10.1137/S0097539704445226
arXiv:quant-ph/0406180

[3] R. Oliveiraand B. M. Terhal ``The complexity of quantum spin systems on a two-dimensional square lattice'' Quantum Information & 1-23 (2005).
arXiv:quant-ph/0504050

[4] D. Aharonov, W. Van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, ``Adiabatic quantum computation is equivalent to standard quantum computation'' SIAM review 50, 755-787 (2008).
https://doi.org/10.1137/080734479
arXiv:quant-ph/0405098

[5] J. Biamonteand P. Love ``Realizable H'' Physical Review A 78, 012352 (2008).
https://doi.org/10.1103/PhysRevA.78.012352
arXiv:1311.3161

[6] D. Aharonov, D. Gottesman, S. Irani, and J. 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] T. Cubittand A. Montanaro ``Complexity classification of local H'' SIAM Journal on Computing 45, 268-316 (2016).
https://doi.org/10.1137/140998287
arXiv:0704.1287

[8] D. Aharonov, I. Arad, and T. Vidick, ``Guest column: the quantum PCP'' Acm SIGACT news 44, 47-79 (2013).
https://doi.org/10.1145/2491533.2491549

[9] R. P. Feynman ``Quantum Mechanical Computers'' Optics News 11, 11 (1985).
https://doi.org/10.1364/ON.11.2.000011

[10] D. Gossetand D. 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] D. Gottesmanand S. 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] N. P. Breuckmannand B. 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] S. Hallgren, D. Nagaj, and S. Narayanaswami, ``The Local H'' Quantum Information and Computation 13, 28 (2013).
arXiv:1312.1469

[14] D. Nagaj ``Tick-tock G'' (2014).
https:/​/​www.youtube.com/​watch?v=ADPzjtt6V04

[15] J. Bausch, T. Cubitt, and M. 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] N. Usher, M. J. Hoban, and D. 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] L. Caha, Z. Landau, and D. 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] D. Aharonov, I. Arad, Z. Landau, and U. 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

[19] J. Bausch ``Quantum Stochastic Processes and Quantum Many-Body Physics'' thesis (2017).
https://doi.org/10.17863/CAM.16755

[20] J. Kelner ``18.409, Topics in Theoretical Computer Science: An Algorithmist's Toolkit''.

[21] A. Peres ``Reversible logic and quantum computers'' Physical Review A 32, 3266-3276 (1985).
https://doi.org/10.1103/PhysRevA.32.3266

[22] A. Gantiand R. Somma ``On the gap of H'' International Journal of Quantum Information 11, 1350063 (2013).
https://doi.org/10.1142/S0219749913500639
arXiv:1307.4993

[23] T. Cubitt ``Lecture notes in A'' (2015).

[24] D. A. Levin, Y. Peres, and E. L. Wilmer, ``Markov chains and mixing times'' American Mathematical Soc. (2009).

[25] J. Cheeger ``A lower bound for the smallest eigenvalue of the L'' Princeton Univ. Press, Princeton, N. J. (1970).

[26] A. Sinclairand M. Jerrum ``Approximate counting, uniform generation and rapidly mixing M'' Information and Computation 82, 93-133 (1989).
https://doi.org/10.1016/0890-5401(89)90067-9

[27] D. Aharonovand T. Naveh ``Quantum NP'' (2002).
arXiv:quant-ph/0210077

[28] T. Albashand D. A. Lidar ``Adiabatic quantum computation'' Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
arXiv:1611.04471

[29] E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, and P. Shor, ``Unstructured Randomness, Small Gaps and Localization'' Quantum Information & 11 (2011).
arXiv:1010.0009

[30] C. 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] S. Bravyi, A. Bessen, and B. Terhal, ``Merlin-A'' (2006).
arXiv:quant-ph/0611021

[32] S. Bravyiand B. Terhal ``Complexity of stoquastic frustration-free H'' Siam journal on computing 39, 1462-1485 (2009).
https://doi.org/10.1137/08072689X
arXiv:0806.1746

[33] G.-Y. Chenand L. 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
http:/​/​arxiv.org/​abs/​1304.4346

► Cited by (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.