Commuting quantum circuits and complexity of Ising partition functions
Open accessThe DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Abstract
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to 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 calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · cited 1×
“lity to offer substantial advantages in solving some sorts of mathematical problems and also in simulating physical dynamics of quantum systems. A representative instance is Shor’s factoring algorithm [1], which solves integer factoring problems in polynomial time, while no polynomial-time classical algorithm has been…”
MethodOn computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283 · cited 1×
“re precisely, BQP (bounded-error quantum polynomial-time computation [8]), can solve problems outside the polynomial hierarchy (PH[9, 10]) [11]. These results strike the extended Church-Turing thesis [12, 13, 8], which states that every reasonable physical computing devices can be simulated efficiently (with a 1 polynom…”
BackgroundRaussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Carolan, J., Harrold, C., Sparrow, C., Martín-López, E., Russell, N. J., Silverstone, J. W., Shadbolt, P. J., Matsuda, N., Oguma, M., Itoh, M., et al. (2015) · Science · doi:10.1126/science.aab3642 · Cited by 1,093 · cited 1×
“) This result brings a novel perspective on linear optical quantum computation and drives many researchers into the recent proof-of-principle experiments [ 21 – 28 ] .”
BackgroundThe computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Boson Sampling on a Photonic Chip
Spring, J. B., Metcalf, B. J., Humphreys, P. C., Kolthammer, W. S., Jin, X.-M., Barbieri, M., Datta, A., Thomas-Peter, N., Langford, N. K., Kundys, D., et al. (2013) · Science · doi:10.1126/science.1231692 · Cited by 837
Stabilizer Codes and Quantum Error Correction
Gottesman, D. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9705052 · Cited by 753
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709
Integrated multimode interferometers with arbitrary designs for photonic boson sampling
Crespi, A., Osellame, R., Ramponi, R., Brod, D. J., Galvão, E. F., Spagnolo, N., Vitelli, C., Maiorino, E., Mataloni, P., & Sciarrino, F. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.112 · Cited by 662
Photonic Boson Sampling in a Tunable Circuit
Broome, M. A., Fedrizzi, A., Rahimi-Keshari, S., Dove, J., Aaronson, S., Ralph, T. C., & White, A. G. (2013) · Science · doi:10.1126/science.1231440 · Cited by 634 · cited 1×
“pses at the third level, which unlikely occurs. This result brings a novel perspective on linear optical quantum computation and drives many researchers into the recent proof-of-principle experiments [13, 14, 15, 16]. Another subclass of quantum computation of this kind is instantaneous quantum polynomialtime computat…”
BackgroundFault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
Universal Blind Quantum Computation
Broadbent, A., Fitzsimons, J., & Kashefi, E. (2009) · 2009 50th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.36 · Cited by 521
Classical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329
Experimental validation of photonic boson sampling
Spagnolo, N., Vitelli, C., Bentivegna, M., Brod, D. J., Crespi, A., Flamini, F., Giacomini, S., Milani, G., Ramponi, R., Mataloni, P., et al. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.135 · Cited by 312
Quantum Circuits That Can Be Simulated Classically in Polynomial Time
Valiant, L. G. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700377025 · Cited by 311
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., & Shepherd, D. J. (2011) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2010.0301 · Cited by 308
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299
Experimental scattershot boson sampling
Bentivegna, M., Spagnolo, N., Vitelli, C., Flamini, F., Viggianiello, N., Latmiral, L., Mataloni, P., Brod, D. J., Galvão, E. F., Crespi, A., et al. (2015) · Science Advances · doi:10.1126/sciadv.1400255 · Cited by 239
Fault-tolerant quantum computation with cluster states
Nielsen, M. A., & Dawson, C. M. (2005) · Physical Review A · doi:10.1103/physreva.71.042323 · Cited by 161 · cited 1×
“If the error ǫ is sufficiently smaller than the threshold value of faulttolerant quantum computation [80, 81, 82], we can reliably simulate universal quantum computation (i.”
MethodCompleteness of the Classical 2D Ising Model and Universal Quantum Computation
Van den Nest, M., Dür, W., & Briegel, H. J. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.110501 · Cited by 63
Classical Spin Models and the Quantum-Stabilizer Formalism
den Nest, M. V., Dür, W., & Briegel, H. J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.117207 · Cited by 56
Quantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
Quantum algorithms for classical lattice models
De las Cuevas, G., Dür, W., Van den Nest, M., & Martin-Delgado, M. A. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/9/093021 · Cited by 40 · cited 1×
“Recently, quantum algorithms for approximating Jones polynomial [2, 3], Tutte polynomial [4], and Ising partition functions [5–7] have been found, and they are shown to beBQP-complete in certain parameter regions.”
MethodLidar, D. A. (2004) · New Journal of Physics · doi:10.1088/1367-2630/6/1/167 · Cited by 33
Cited by
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299
The Born supremacy: quantum advantage and training of an Ising Born machine
Coyle, B., Mills, D., Danos, V., & Kashefi, E. (2020) · npj Quantum Information · doi:10.1038/s41534-020-00288-9 · Cited by 155
“With the restrictions set discussed above, the term in the exponent of the diagonal unitary (18) can be written as an Ising Model Hamiltonian, [32, 35]: ∑”
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Metadata
- Authors
- Fujii, K., & Morimae, T.
- Venue
- New Journal of Physics
- Publisher
- IOP Publishing
- Published
- 2017-03-01
- Volume
- 19
- Issue
- 3
- Pages
- 033003
- ISSN
- 1367-2630 (ISSN-L)
- OpenAlex
- W2128785157
- Cited by
- 48
- References
- 27
- FWCI
- 3.61
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.