2013

Quantum Commuting Circuits and Complexity of Ising Partition Functions

Fujii, Keisuke, Morimae, Tomoyuki

Understand

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal in the sense of standard quantum computation.

Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy (PH) collapses at the third level, which is highly implausible.
However, the origin of the classical intractability is still less understood.
Here we establish a relationship between IQP and computational complexity of the partition functions of Ising models.

Built on

A. Church, “A set of postulates for the foundation of logic,” The Annals of Mathematics
1932
Earlier work this paper cites.
A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London mathematical society
1936
Earlier work this paper cites.
P. W. Kasteleyn, “The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice,” Physica
1961
Earlier work this paper cites.
M. E. Fisher, “On the dimer solution of planar ising models,” Journal of Mathematical Physics
1966
Earlier work this paper cites.
L. G. Valiant, “The complexity of computing the permanent,” Theoretical computer science
1979
Earlier work this paper cites.
F. Barahona, “On the computational complexity of Ising spin glass models,” Journal of Physics A: Mathematical and General
1982
Earlier work this paper cites.
S. Toda, “PP is as hard as the polynomial-time hierarchy,” SIAM Journal on Computing
1991
Earlier work this paper cites.
E. Bernstein and U. Vazirani, “Quantum complexity theory,” in Proceedings of the twenty-fifth annual ACM symposium on Theory of computing
1993
Earlier work this paper cites.
M. Jerrum and A. Sinclair, “Polynomial-time approximation algorithms for the ising model,” SIAM Journal on computing
1993
Earlier work this paper cites.
M. Jerrum and A. Sinclair, “Polynomial-time approximation algorithms for the ising model,” SIAM Journal on computing
1993
Earlier work this paper cites.
P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science
1994
Earlier work this paper cites.
Addison Wesley, 1994
C. H. Papadimitriou, Computational Complexity · 1994
Earlier work this paper cites.
R. Beigel, N. Reingold, and D. Spielman, “Pp is closed under intersection,” Journal of Computer and System Sciences
1995
Earlier work this paper cites.
D. Zuckerman, “On unapproximable versions of np-complete problems,” SIAM Journal on Computing
1996
Earlier work this paper cites.
PhD thesis, California Institute of Technology, 1997
D. Gottesman, Stabilizer codes and quantum error correction · 1997
Earlier work this paper cites.
D. A. Lidar and O. Biham, “Simulating ising spin glasses on a quantum computer,” Physical Review E
1997
Earlier work this paper cites.
D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant error,” in Proceedings of the twenty-ninth annual ACM symposium on Theory of computing
1997
Earlier work this paper cites.
E. Knill and R. Laflamme, “Power of one bit of quantum information,” Physical Review Letters
1998
Earlier work this paper cites.
D. Aharonov, A. Kitaev, and N. Nisan, “Quantum circuits with mixed states,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing
1998
Earlier work this paper cites.
Cambridge university press, 2000
M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information · 2000
Earlier work this paper cites.
S. Istrail, “Statistical mechanics, three-dimensionality and NP-completeness: I. universality of intracatability for the partition function of the Ising model across non-planar surfaces,” in Proceedings of the thirty-second annual ACM symposium on Theory of computing
2000
Earlier work this paper cites.
R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” Physical Review Letters
2001
Earlier work this paper cites.
E. Knill, “Fermionic linear optics and matchgates,” arXiv preprint quant-ph/0108033
2001
Earlier work this paper cites.
E. Knill, R. Laflamme, and G. J. Milburn, “A scheme for efficient quantum computation with linear optics,” nature
2001
Earlier work this paper cites.
E. Knill and R. Laflamme, “Quantum computing and quadratically signed weight enumerators,” Information Processing Letters
2001
Earlier work this paper cites.
L. G. Valiant, “Quantum circuits that can be simulated classically in polynomial time,” SIAM Journal on Computing
2002
Earlier work this paper cites.
B. M. Terhal and D. P. DiVincenzo, “Classical simulation of noninteracting-fermion quantum circuits,” Physical Review A
2002
Earlier work this paper cites.
C. P. Master, F. Yamaguchi, and Y. Yamamoto, “Efficiency of free-energy calculations of spin lattices by spectral quantum algorithms,” Physical Review A
2003
Earlier work this paper cites.

Similar

A. Y. Kitaev, “Fault-tolerant quantum computation by anyons,” Annals of Physics
2003
Cited alongside, same era.
PhD thesis, Ludwig-Maximillians Universität München, 2003
R. Raussendorf, Measurement-based quantum computation with cluster states · 2003
Cited alongside, same era.
D. A. Lidar, “On the quantum computational complexity of the ising spin glass partition function and of knot invariants,” New Journal of Physics
2004
Cited alongside, same era.
S. Aaronson, “Quantum computing, postselection, and probabilistic polynomial-time,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science
2005
Cited alongside, same era.
P. Sen, “Random measurement bases, quantum state distinction and applications to the hidden subgroup problem,” in Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
2005
Cited alongside, same era.
M. A. Nielsen and C. M. Dawson, “Fault-tolerant quantum computation with cluster states,” Physical Review A
2005
Cited alongside, same era.
D. Aharonov and I. Arad, “The BQP-hardness of approximating the Jones polynomial,” arXiv preprint quant-ph/0605181
2006
Cited alongside, same era.
M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H. Briegel, “Quantum computers, algorithms and chaos,” in International School of Physics Enrico Fermi
2006
Cited alongside, same era.
D. Aharonov, I. Arad, E. Eban, and Z. Landau, “Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane,” arXiv preprint quant-ph/0702008
2007
Cited alongside, same era.
L. A. Goldberg and M. Jerrum, “The complexity of ferromagnetic ising with local fields,” Combinatorics, Probability & Computing
2007
Cited alongside, same era.
M. Van den Nest, W. Dür, and H. J. Briegel, “Classical spin models and the quantum-stabilizer formalism,” Physical Review Letters
2007
Cited alongside, same era.
S. Bravyi and R. Raussendorf, “Measurement-based quantum computation with the toric code states,” Physical Review A
2007
Cited alongside, same era.

Then

S. Aaronson, “A linear-optical proof that the permanent is# p-hard,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science
2011
Later among the works it cites.
M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science
2011
Later among the works it cites.
No. 2 in Graduate Surveys, Theory of Computing Library, 2011
A. Drucker and R. de Wolf, Quantum Proofs for Classical Theorems · 2011
Later among the works it cites.
A. Sly and N. Sun, “The computational hardness of counting in two-spin models on d-regular graphs,” in Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
2012
Later among the works it cites.
L. Goff and R. Raussendorf, “Classical simulation of measurement-based quantum computation on higher-genus surface-code states,” Phys. Rev. A
2012
Later among the works it cites.
A. Sinclair, P. Srivastava, and M. Thurley, “Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs,” in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms
2012
Later among the works it cites.
R. Jozsa and M. Van den Nest, “Classical simulation complexity of extended Clifford circuits,” arXiv preprint arXiv:1305.6190
Original
2013
Closest in time.
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, “Photonic boson sampling in a tunable circuit,” Science
2013
Closest in time.
J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, et al
2013
Closest in time.
M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental boson sampling,” Nature Photonics
2013
Closest in time.
A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, “Integrated multimode interferometers with arbitrary designs for photonic boson sampling,” Nature Photonics
2013
Closest in time.
S. Aaronson and A. Arkhipov, “Bosonsampling is far from uniform,” arXiv preprint arXiv:1309.7460
Original
2013
Closest in time.
M. J. Hoban, J. J. Wallman, H. Anwar, N. Usher, R. Raussendorf, and D. E. Browne, “On the hardness of sampling and measurement-based classical computation,” arXiv preprint arXiv:1304.2667
Original
2013
Closest in time.
T. Morimae and K. Fujii, “Blind quantum computation protocol in which Alice only makes measurements,” Physical Review A
2013
Closest in time.
X. Ni and M. Van den Nest, “Commuting quantum circuits: efficient classical simulations versus hardness results,” Quantum Information and Computation
2013
Closest in time.
Y. Nakata and M. Murao, “Diagonal-unitary 2-design and their implementations by quantum circuits,” International Journal of Quantum Information
2013
Closest in time.
K. Fujii, “Quantum information and statistical mechanics: an introduction to frontier,” arXiv preprint arXiv:1306.6757
Original
2013
Closest in time.
S. Iblisdir, M. Cirio, O. Boada, and G. Brennen, “Low depth quantum circuits for ising models,” Annals of Physics
2014
Closest in time.
A. Matsuo, K. Fujii, and N. Imoto, “A quantum algorithm for additive approximation of ising partition functions,” arXiv preprint arXiv:1405.2749
Original
2014
Closest in time.
J. Carolan, J. D. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. Matthews, et al
2014
Closest in time.
N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, et al
2014
Closest in time.
Y. Nakata and M. Murao, “Diagonal quantum circuits: their computational power and applications,” arXiv preprint arXiv:1405.6552
Original
2014
Closest in time.
Y. Nakata, M. Koashi, and M. Murao, “Generating a state t-design by diagonal quantum circuits,” New Journal of Physics
2014
Closest in time.
L. A. Goldberg and H. Guo, “The complexity of approximating complex-valued ising and tutte partition functions,” arXiv preprint arXiv:1409.5627
Original
2014
Closest in time.
M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvão, A. Crespi, et al
2015
Closest in time.
J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, et al
2015
Closest in time.
K. Fujii and S. Tamate, “Computational quantum-classical boundary of noisy commuting quantum circuits,” Scientific reports
2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…