Two-local qubit Hamiltonians: when are they stoquastic?

Joel Klassen1 and Barbara M. Terhal1,2

1QuTech, Delft University of Technology, P.O. Box 5046, 2600 GA Delft, The Netherlands
2Institute for Theoretical Nanoelectronics, Forschungszentrum Juelich, D-52425 Juelich, Germany

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


We examine the problem of determining if a 2-local Hamiltonian is stoquastic by local basis changes. We analyze this problem for two-qubit Hamiltonians, presenting some basic tools and giving a concrete example where using unitaries beyond Clifford rotations is required in order to decide stoquasticity. We report on simple results for $n$-qubit Hamiltonians with identical 2-local terms on bipartite graphs. Our most significant result is that we give an efficient algorithm to determine whether an arbitrary $n$-qubit XYZ Heisenberg Hamiltonian is stoquastic by local basis changes.

► BibTeX data

► References

[1] S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, ``The Complexity of Stoquastic Local Hamiltonian Problems,'' Quantum Information and Computation 8 no. 5, (2008) 0361–0385 , arXiv:0606140 [quant-ph].

[2] N. J. Cerf and O. C. Martin, ``Projection Monte Carlo methods : an algorithmic analysis,'' International Journal of Modern Physics C 6 no. 5, (1995) 693–723.

[3] S. Sorella and L. Capriotti, ``Green function Monte Carlo with stochastic reconfiguration: An effective remedy for the sign problem,'' Physical Review B - Condensed Matter and Materials Physics 61 no. 4, (2000) 2599–2612, arXiv:9902211 [cond-mat].

[4] S. Bravyi, ``Monte Carlo Simulation of Stoquastic Hamiltonians,'' Quantum Information and Computation 15 no. 13/​14, (2015) 1122–1140, arXiv:1402.2295.

[5] S. Wessel, ``Monte Carlo Simulations of Quantum Spin Models Institute for Theoretical Solid State Physics,'' in Autumn School on Correlated Electrons. 2013. https:/​/​​events/​correl13/​manuscripts/​.

[6] E. Crosson, Classical and Quantum Computation in Ground States and Beyond. PhD thesis, University of Washington, 2015. http:/​/​​1773/​34128.

[7] S. Bravyi and D. Gosset, ``Polynomial-Time Classical Simulation of Quantum Ferromagnets,'' Physical Review Letters 119 no. 10, (2017) , arXiv:1612.05602.

[8] T. Albash and D. A. Lidar, ``Adiabatic quantum computation,'' Reviews of Modern Physics 90 no. 1, (2018) 015002, arXiv:1611.04471 [quant-ph].

[9] S. Bravyi and B. Terhal, ``Complexity of stoquastic frustration-free Hamiltonians,'' SIAM J. Comput. 39 no. 4, (2009) 1642, arXiv:0806.1746.

[10] M. B. Hastings and M. H. Freedman, ``Obstructions To Classically Simulating The Quantum Adiabatic Algorithm,'' Quantum Information and Computation 13 no.11/​12, (2013) 1038-1076 arXiv:1302.5733.

[11] J. Bringewatt, W. Dorland, S. P. Jordan, and A. Mink, ``Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians,'' Phys. Rev. A 97 no. 2, (Feb., 2018) 022323, arXiv:1709.03971 [quant-ph].

[12] D. Kafri, C. Quintana, Y. Chen, A. Shabani, J. M. Martinis, and H. Neven, ``Tunable inductive coupling of superconducting qubits in the strongly nonlinear regime,'' Physical Review A 95 no. 5, (May, 2017) 052333, arXiv:1606.08382.

[13] L. Hormozi, E. W. Brown, G. Carleo, and M. Troyer, ``Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass,'' Phys. Rev. B 95 no. 18, (May, 2017) 184416, arXiv:1609.06558 [quant-ph].

[14] G. Samach, ``Tunable XX-Coupling Between High Coherence Flux Qubits,'' in APS March Meeting 2018. 2018. https:/​/​​Meeting/​MAR18/​Session/​L33.13.

[15] V. I. Iglovikov, E. Khatami, and R. T. Scalettar, ``Geometry dependence of the sign problem in quantum Monte Carlo simulations,'' Phys. Rev. B 92 (Jul, 2015) 045110. https:/​/​​doi/​10.1103/​PhysRevB.92.045110.

[16] C. Wu and S.-C. Zhang, ``Sufficient condition for absence of the sign problem in the fermionic quantum monte carlo algorithm,'' Phys. Rev. B 71 (Apr, 2005) 155115.

[17] Z.-X. Li and H. Yao, ``Sign-Problem-Free Fermionic Quantum Monte Carlo: Developments and Applications,'' arXiv e-prints (May, 2018) arXiv:1805.08219, arXiv:1805.08219 [cond-mat.str-el].

[18] R. F. Bishop and D. J. J. Farnell, ``Marshall-Peierls sign rules, the quantum monte carlo method, and frustration,'' International Journal of Modern Physics B 15 no. 10n11, (2001) 1736–1739.

[19] M. Marvian, D. A. Lidar, and I. Hen, ``On the Computational Complexity of Curing non-stoquastic Hamiltonians,'' Nature Communications 10 no. 1, (2019) 1571 , arXiv:1802.03408.

[20] B. M. Terhal, ``The Power and Use of Stoquastic Hamiltonians,'' in Adiabatic Quantum Computing Conference. 2017. https:/​/​​watch?v=4dK30QExF4M.

[21] T. Cubitt, A. Montanaro, and S. Piddock, ``Universal Quantum Hamiltonians,'' National Academy of Sciences 115 no. 38 (2018) 9497-9502 , arXiv:1701.05182.

[22] S. Bravyi and M. Hastings, ``On complexity of the quantum Ising model,'' Communications in Mathematical Physics 349 no. 1 (2017) 1-45 , arXiv:1410.0703 [quant-ph].

[23] D. Grier and L. Schaeffer, ``The Classification of Stabilizer Operations over Qubits,'' ArXiv e-prints (Mar., 2016) , arXiv:1603.03999 [quant-ph].

[24] Y. Makhlin, ``Nonlocal properties of two-qubit gates and mixed states and optimization of quantum computations,'' Quantum Information Processing 1 no. 4, (2002) 243–252, arXiv:0002045 [quant-ph].

[25] N. Linden, S. Popescu, and A. Sudbery, ``Nonlocal Parameters for Multiparticle Density Matrices,'' Physical Review Letters 83 no. 2, (1999) 243–247, arXiv:9801076 [quant-ph].

[26] M. Grassl, M. Rötteler, and T. Beth, ``Computing local invariants of quantum-bit systems,'' Phys. Rev. A 58 (Sept., 1998) 1833–1839, quant-ph/​9712040.

[27] R. A. Bertlmann and P. Krammer, ``Bloch vectors for qudits,'' Journal of Physics A: Mathematical and Theoretical 41 no. 23, (2008) , arXiv:0806.1174.

[28] T. F. Gonzalez, ``Clustering to minimize the maximum intercluster distance,'' Theoretical Computer Science 38 (1985) 293–306.

Cited by

[1] Giacomo Torlai, Juan Carrasquilla, Matthew T. Fishman, Roger G. Melko, and Matthew P. A. Fisher, "Wave-function positivization via automatic differentiation", Physical Review Research 2 3, 032060 (2020).

[2] Dominik Hangleiter, Ingo Roth, Daniel Nagaj, and Jens Eisert, "Easing the Monte Carlo sign problem", arXiv:1906.02309, Science Advances 6 33, eabb8341 (2020).

[3] A. Ciani and B. M. Terhal, "Stoquasticity in circuit QED", Physical Review A 103 4, 042401 (2021).

[4] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver, "Perspectives of quantum annealing: methods and implementations", Reports on Progress in Physics 83 5, 054401 (2020).

[5] Gioele Consani and Paul A Warburton, "Effective Hamiltonians for interacting superconducting qubits: local basis reduction and the Schrieffer–Wolff transformation", New Journal of Physics 22 5, 053040 (2020).

[6] Andrew J Kerman, "Superconducting qubit circuit emulation of a vector spin-1/2", New Journal of Physics 21 7, 073030 (2019).

[7] Lalit Gupta and Itay Hen, "Elucidating the Interplay between Non‐Stoquasticity and the Sign Problem", Advanced Quantum Technologies 3 1, 1900108 (2020).

[8] I. Ozfidan, C. Deng, A.Y. Smirnov, T. Lanting, R. Harris, L. Swenson, J. Whittaker, F. Altomare, M. Babcock, C. Baron, A.J. Berkley, K. Boothby, H. Christiani, P. Bunyk, C. Enderud, B. Evert, M. Hager, A. Hajda, J. Hilton, S. Huang, E. Hoskinson, M.W. Johnson, K. Jooya, E. Ladizinsky, N. Ladizinsky, R. Li, A. MacDonald, D. Marsden, G. Marsden, T. Medina, R. Molavi, R. Neufeld, M. Nissen, M. Norouzpour, T. Oh, I. Pavlov, I. Perminov, G. Poulin-Lamarre, M. Reis, T. Prescott, C. Rich, Y. Sato, G. Sterling, N. Tsai, M. Volkmann, W. Wilkinson, J. Yao, and M.H. Amin, "Demonstration of a Nonstoquastic Hamiltonian in Coupled Superconducting Flux Qubits", Physical Review Applied 13 3, 034037 (2020).

[9] Adrian Chapman and Steven T. Flammia, "Characterization of solvable spin models via graph invariants", Quantum 4, 278 (2020).

[10] Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner, "A Quantum N-Queens Solver", Quantum 3, 149 (2019).

[11] 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).

[12] Tameem Albash, "Validating a two-qubit nonstoquastic Hamiltonian in quantum annealing", Physical Review A 101 1, 012310 (2020).

[13] Dorit Aharonov and Alex B. Grilo, "Stoquastic PCP vs. Randomness", arXiv:1901.05270.

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 08:05:21) and SAO/NASA ADS (last updated successfully 2021-04-21 08:05:22). The list may be incomplete as not all publishers provide suitable and complete citation data.