DOI: 10.22331/q-2017-04-25-8. Achieving quantum supremacy with sparse and noisy commuting quantum computations

Achieving quantum supremacy with sparse and noisy commuting quantum computations

10.22331/q-2017-04-25-8

Crossref journal-article

Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften

Quantum (9598)

Abstract

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.

Bibliography

Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017). Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1, 8.

Authors 3

Michael J. Bremner (first)
Ashley Montanaro (additional)
Dan J. Shepherd (additional)

References 44 Referenced 125

S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9 (4): 143-252, 2013. arXiv:1011.3245. (10.1145/1993636.1993682)
N. Alon, A. Frieze, and D. Welsh. Polynomial time randomized approximation schemes for the Tutte polynomial of dense graphs. In Proc. 35th Annual Symp. Foundations of Computer Science, 1994, page 24. (10.1109/SFCS.1994.365708)
A. Arkhipov. BosonSampling is robust to small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. arXiv:1412.2516. (10.1103/PhysRevA.92.062326)
S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58: 193-210, 1999. (10.1145/225058.225140)
R. Beals, S. Brierley, O. Gray, A. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather. Efficient distributed quantum computing. Proc. Roy. Soc. A, 469: 20120686, 2013. arXiv:1207.2307. (10.1098/rspa.2012.0686)
J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing quantum supremacy, 2017. arXiv:1703.00466. (10.1103/PhysRevX.8.021010)
S. Boixo, S. Isakov, V. Smelyanskiy, R. Babbush, N. Ding, Z. Jian, J. Martinis, and H. Neven. Characterizing quantum supremacy in near-term devices, 2016. arXiv:1608.00263.
B. Bollobás. The distribution of the maximum degree of a random graph. Discrete Mathematics, 32: 201-203, 1980. (10.1016/0012-365X(80)90054-0)
C. Brand, H. Dell, and M. Roth. Fine-grained dichotomies for the Tutte plane and Boolean ĊSP, 2016. arXiv:1606.06581.
M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. Ser. A, 467 (2126): 459-472, 2011. arXiv:1005.1407. (10.1098/rspa.2010.0301)
M. Bremner, A. Montanaro, and D. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, 2016. arXiv:1504.07999. (10.1103/PhysRevLett.117.080501)
W. Brown and O. Fawzi. Scrambling speed of random quantum circuits, 2012. arXiv:1210.6644.
W. Brown and O. Fawzi. Decoupling with random quantum circuits. Comm. Math. Phys., 340 (3): 867-900, 2015. arXiv:1307.0632. (10.1007/s00220-015-2470-1)
H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger. New limits on fault-tolerant quantum computation. In Proc. 47th Annual Symp. Foundations of Computer Science, 2006, pages 411-419. quant-ph/0604141. (10.1109/FOCS.2006.50)
R. Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. In Proc. 42nd International Conference on Automata, Languages and Programming (ICALP'15), 2015, pages 380-392. arXiv:1511.02910. (10.1007/978-3-662-47672-7_31)
R. Diestel. Graph Theory. Springer, 2010. (10.1007/978-3-642-14279-6)
D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. (10.1017/CBO9780511581274)
E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028.
E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. arXiv:1412.6062.
E. Farhi and A. Harrow. Quantum supremacy through the Quantum Approximate Optimization Algorithm, 2016. arXiv:1602.07674.
K. Fujii and S. Tamate. Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports, 6: 25598, 2016. arXiv:1406.6932. (10.1038/srep25598)
X. Gao, S.-T. Wang, and L.-M. Duan. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett., 118: 040502, 2017. arXiv:1607.04947. (10.1103/PhysRevLett.118.040502)
D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert. Direct certification of a class of quantum simulations. Quantum Science and Technology, 1 (2), 2017. arXiv:1602.00703. (10.1088/2058-9565/2/1/015004)
G. Kalai. The quantum computer puzzle. Notices of the AMS, 63 (5): 508-516, 2016. arXiv:1605.00992. (10.1090/noti1380)
G. Kalai and G. Kindler. Gaussian noise sensitivity and BosonSampling, 2014. arXiv:1409.3093.
J. Kempe, O. Regev, F. Unger, and R. de Wolf. Upper bounds on the noise threshold for fault-tolerant quantum computing. In Proc. 35th International Conference on Automata, Languages and Programming (ICALP'08), 2008, pages 845-856. arXiv:0802.1464. (10.1007/978-3-540-70575-8_69)
E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. In Proc. 23rd Annual ACM Symp. Theory of Computing, 1991, pages 455-464. (10.1137/0222080)
A. Leverrier and R. García-Patrón. Analysis of circuit imperfections in BosonSampling. Quantum Inf. Comput., 15: 0489-0512, 2015. arXiv:1309.4687. (10.26421/QIC15.5-6-8)
I. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM J. Comput., 38: 963-981, 2008. quant-ph/0511069. (10.1137/050644756)
M. Marvian and D. Lidar. Error suppression for Hamiltonian-based quantum computation using subsystem codes, 2016. arXiv:1606.03795. (10.1103/PhysRevLett.118.030504)
T. Morimae, K. Fujii, and J. Fitzsimons. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, 2014. arXiv:1312.2496. (10.1103/PhysRevLett.112.130502)
R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. (10.1017/CBO9781139814782)
J. Preskill. Quantum computing and the entanglement frontier, 2012. arXiv:1203.5813.
S. Rahimi-Keshari, T. Ralph, and C. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6: 021039, 2016. arXiv:1511.06526. (10.1103/PhysRevX.6.021039)
A. Razborov. An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput., 4 (3): 222-228, 2004. quant-ph/0310136. (10.26421/QIC4.3-7)
T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge University Press, 2008. (10.1017/CBO9780511791338)
C. Schnorr and A. Shamir. An optimal sorting algorithm for mesh connected computers. In Proc. 18th Annual ACM Symp. Theory of Computing, 1986, pages 255-263. (10.1145/12130.12156)
M. Schwarz and M. Van den Nest. Simulating quantum circuits with sparse output distributions, 2013. arXiv:1310.6749.
V. Shchesnovich. Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal BosonSampling. Phys. Rev. A, 91: 063842, 2015. arXiv:1501.00850. (10.1103/PhysRevA.91.063842)
D. Shepherd. Binary matroids and quantum probability distributions, 2010. arXiv:1005.1744.
D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proc. Roy. Soc. Ser. A, 465 (2105): 1413-1439, 2009. arXiv:0809.0847. (10.1098/rspa.2008.0443)
D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26: 1474-1483, 1997. (10.1137/S0097539796298637)
S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20 (5): 865-877, 1991. (10.1137/0220053)
S. Virmani, S. Huelga, and M. Plenio. Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71: 042328, 2005. quant-ph/0408076. (10.1103/PhysRevA.71.042328)

Dates

Type	When
Created	8 years, 4 months ago (April 25, 2017, 5:05 a.m.)
Deposited	2 years ago (Aug. 23, 2023, 3:52 a.m.)
Indexed	5 days, 19 hours ago (Aug. 20, 2025, 8:55 a.m.)
Issued	8 years, 4 months ago (April 25, 2017)
Published	8 years, 4 months ago (April 25, 2017)
Published Online	8 years, 4 months ago (April 25, 2017)

Funders 0

None

BibTeX

@article{Bremner_2017, title={Achieving quantum supremacy with sparse and noisy commuting quantum computations}, volume={1}, ISSN={2521-327X}, url={http://dx.doi.org/10.22331/q-2017-04-25-8}, DOI={10.22331/q-2017-04-25-8}, journal={Quantum}, publisher={Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften}, author={Bremner, Michael J. and Montanaro, Ashley and Shepherd, Dan J.}, year={2017}, month=apr, pages={8} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        20
      ]
    ],
    "date-time": "2025-08-20T12:55:43Z",
    "timestamp": 1755694543634
  },
  "reference-count": 44,
  "publisher": "Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2017,
            4,
            25
          ]
        ],
        "date-time": "2017-04-25T00:00:00Z",
        "timestamp": 1493078400000
      },
      "content-version": "unspecified",
      "delay-in-days": 0,
      "URL": "https://creativecommons.org/licenses/by/4.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "abstract": "<jats:p>The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.</jats:p>",
  "DOI": "10.22331/q-2017-04-25-8",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2017,
        4,
        25
      ]
    ],
    "date-time": "2017-04-25T09:05:12Z",
    "timestamp": 1493111112000
  },
  "page": "8",
  "source": "Crossref",
  "is-referenced-by-count": 125,
  "title": "Achieving quantum supremacy with sparse and noisy commuting quantum computations",
  "prefix": "10.22331",
  "volume": "1",
  "author": [
    {
      "given": "Michael J.",
      "family": "Bremner",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia"
        }
      ]
    },
    {
      "given": "Ashley",
      "family": "Montanaro",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "School of Mathematics, University of Bristol, UK"
        }
      ]
    },
    {
      "given": "Dan J.",
      "family": "Shepherd",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "3NCSC, Hubble Road, Cheltenham, UK"
        }
      ]
    }
  ],
  "member": "9598",
  "published-online": {
    "date-parts": [
      [
        2017,
        4,
        25
      ]
    ]
  },
  "reference": [
    {
      "key": "1",
      "doi-asserted-by": "publisher",
      "unstructured": "S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing, 9 (4): 143-252, 2013. arXiv:1011.3245.",
      "DOI": "10.1145/1993636.1993682"
    },
    {
      "key": "2",
      "doi-asserted-by": "publisher",
      "unstructured": "N. Alon, A. Frieze, and D. Welsh. Polynomial time randomized approximation schemes for the Tutte polynomial of dense graphs. In Proc. 35th Annual Symp. Foundations of Computer Science, 1994, page 24.",
      "DOI": "10.1109/SFCS.1994.365708"
    },
    {
      "key": "3",
      "doi-asserted-by": "publisher",
      "unstructured": "A. Arkhipov. BosonSampling is robust to small errors in the network matrix. Phys. Rev. A, 92: 062326, 2015. arXiv:1412.2516.",
      "DOI": "10.1103/PhysRevA.92.062326"
    },
    {
      "key": "4",
      "doi-asserted-by": "publisher",
      "unstructured": "S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58: 193-210, 1999.",
      "DOI": "10.1145/225058.225140"
    },
    {
      "key": "5",
      "doi-asserted-by": "publisher",
      "unstructured": "R. Beals, S. Brierley, O. Gray, A. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather. Efficient distributed quantum computing. Proc. Roy. Soc. A, 469: 20120686, 2013. arXiv:1207.2307.",
      "DOI": "10.1098/rspa.2012.0686"
    },
    {
      "key": "6",
      "doi-asserted-by": "crossref",
      "unstructured": "J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing quantum supremacy, 2017. arXiv:1703.00466.",
      "DOI": "10.1103/PhysRevX.8.021010"
    },
    {
      "key": "7",
      "unstructured": "S. Boixo, S. Isakov, V. Smelyanskiy, R. Babbush, N. Ding, Z. Jian, J. Martinis, and H. Neven. Characterizing quantum supremacy in near-term devices, 2016. arXiv:1608.00263."
    },
    {
      "key": "8",
      "doi-asserted-by": "publisher",
      "unstructured": "B. Bollob\u00e1s. The distribution of the maximum degree of a random graph. Discrete Mathematics, 32: 201-203, 1980.",
      "DOI": "10.1016/0012-365X(80)90054-0"
    },
    {
      "key": "9",
      "unstructured": "C. Brand, H. Dell, and M. Roth. Fine-grained dichotomies for the Tutte plane and Boolean \u010aSP, 2016. arXiv:1606.06581."
    },
    {
      "key": "10",
      "doi-asserted-by": "publisher",
      "unstructured": "M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. Ser. A, 467 (2126): 459-472, 2011. arXiv:1005.1407.",
      "DOI": "10.1098/rspa.2010.0301"
    },
    {
      "key": "11",
      "doi-asserted-by": "publisher",
      "unstructured": "M. Bremner, A. Montanaro, and D. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, 2016. arXiv:1504.07999.",
      "DOI": "10.1103/PhysRevLett.117.080501"
    },
    {
      "key": "12",
      "unstructured": "W. Brown and O. Fawzi. Scrambling speed of random quantum circuits, 2012. arXiv:1210.6644."
    },
    {
      "key": "13",
      "doi-asserted-by": "publisher",
      "unstructured": "W. Brown and O. Fawzi. Decoupling with random quantum circuits. Comm. Math. Phys., 340 (3): 867-900, 2015. arXiv:1307.0632.",
      "DOI": "10.1007/s00220-015-2470-1"
    },
    {
      "key": "14",
      "doi-asserted-by": "publisher",
      "unstructured": "H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger. New limits on fault-tolerant quantum computation. In Proc. 47th Annual Symp. Foundations of Computer Science, 2006, pages 411-419. quant-ph/0604141.",
      "DOI": "10.1109/FOCS.2006.50"
    },
    {
      "key": "15",
      "doi-asserted-by": "publisher",
      "unstructured": "R. Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. In Proc. 42nd International Conference on Automata, Languages and Programming (ICALP'15), 2015, pages 380-392. arXiv:1511.02910.",
      "DOI": "10.1007/978-3-662-47672-7_31"
    },
    {
      "key": "16",
      "doi-asserted-by": "crossref",
      "unstructured": "R. Diestel. Graph Theory. Springer, 2010.",
      "DOI": "10.1007/978-3-642-14279-6"
    },
    {
      "key": "17",
      "doi-asserted-by": "crossref",
      "unstructured": "D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.",
      "DOI": "10.1017/CBO9780511581274"
    },
    {
      "key": "18",
      "unstructured": "E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028."
    },
    {
      "key": "19",
      "unstructured": "E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. arXiv:1412.6062."
    },
    {
      "key": "20",
      "unstructured": "E. Farhi and A. Harrow. Quantum supremacy through the Quantum Approximate Optimization Algorithm, 2016. arXiv:1602.07674."
    },
    {
      "key": "21",
      "doi-asserted-by": "publisher",
      "unstructured": "K. Fujii and S. Tamate. Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports, 6: 25598, 2016. arXiv:1406.6932.",
      "DOI": "10.1038/srep25598"
    },
    {
      "key": "22",
      "doi-asserted-by": "publisher",
      "unstructured": "X. Gao, S.-T. Wang, and L.-M. Duan. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett., 118: 040502, 2017. arXiv:1607.04947.",
      "DOI": "10.1103/PhysRevLett.118.040502"
    },
    {
      "key": "23",
      "doi-asserted-by": "publisher",
      "unstructured": "D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert. Direct certification of a class of quantum simulations. Quantum Science and Technology, 1 (2), 2017. arXiv:1602.00703.",
      "DOI": "10.1088/2058-9565/2/1/015004"
    },
    {
      "key": "24",
      "doi-asserted-by": "publisher",
      "unstructured": "G. Kalai. The quantum computer puzzle. Notices of the AMS, 63 (5): 508-516, 2016. arXiv:1605.00992.",
      "DOI": "10.1090/noti1380"
    },
    {
      "key": "25",
      "unstructured": "G. Kalai and G. Kindler. Gaussian noise sensitivity and BosonSampling, 2014. arXiv:1409.3093."
    },
    {
      "key": "26",
      "doi-asserted-by": "publisher",
      "unstructured": "J. Kempe, O. Regev, F. Unger, and R. de Wolf. Upper bounds on the noise threshold for fault-tolerant quantum computing. In Proc. 35th International Conference on Automata, Languages and Programming (ICALP'08), 2008, pages 845-856. arXiv:0802.1464.",
      "DOI": "10.1007/978-3-540-70575-8_69"
    },
    {
      "key": "27",
      "doi-asserted-by": "publisher",
      "unstructured": "E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. In Proc. 23rd Annual ACM Symp. Theory of Computing, 1991, pages 455-464.",
      "DOI": "10.1137/0222080"
    },
    {
      "key": "28",
      "doi-asserted-by": "crossref",
      "unstructured": "A. Leverrier and R. Garc\u00eda-Patr\u00f3n. Analysis of circuit imperfections in BosonSampling. Quantum Inf. Comput., 15: 0489-0512, 2015. arXiv:1309.4687.",
      "DOI": "10.26421/QIC15.5-6-8"
    },
    {
      "key": "29",
      "doi-asserted-by": "publisher",
      "unstructured": "I. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM J. Comput., 38: 963-981, 2008. quant-ph/0511069.",
      "DOI": "10.1137/050644756"
    },
    {
      "key": "30",
      "doi-asserted-by": "crossref",
      "unstructured": "M. Marvian and D. Lidar. Error suppression for Hamiltonian-based quantum computation using subsystem codes, 2016. arXiv:1606.03795.",
      "DOI": "10.1103/PhysRevLett.118.030504"
    },
    {
      "key": "31",
      "doi-asserted-by": "publisher",
      "unstructured": "T. Morimae, K. Fujii, and J. Fitzsimons. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, 2014. arXiv:1312.2496.",
      "DOI": "10.1103/PhysRevLett.112.130502"
    },
    {
      "key": "32",
      "doi-asserted-by": "crossref",
      "unstructured": "R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.",
      "DOI": "10.1017/CBO9781139814782"
    },
    {
      "key": "33",
      "unstructured": "J. Preskill. Quantum computing and the entanglement frontier, 2012. arXiv:1203.5813."
    },
    {
      "key": "34",
      "doi-asserted-by": "publisher",
      "unstructured": "S. Rahimi-Keshari, T. Ralph, and C. Caves. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X, 6: 021039, 2016. arXiv:1511.06526.",
      "DOI": "10.1103/PhysRevX.6.021039"
    },
    {
      "key": "35",
      "doi-asserted-by": "crossref",
      "unstructured": "A. Razborov. An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput., 4 (3): 222-228, 2004. quant-ph/0310136.",
      "DOI": "10.26421/QIC4.3-7"
    },
    {
      "key": "36",
      "doi-asserted-by": "crossref",
      "unstructured": "T. Richardson and R. Urbanke. Modern Coding Theory. Cambridge University Press, 2008.",
      "DOI": "10.1017/CBO9780511791338"
    },
    {
      "key": "37",
      "doi-asserted-by": "publisher",
      "unstructured": "C. Schnorr and A. Shamir. An optimal sorting algorithm for mesh connected computers. In Proc. 18th Annual ACM Symp. Theory of Computing, 1986, pages 255-263.",
      "DOI": "10.1145/12130.12156"
    },
    {
      "key": "38",
      "unstructured": "M. Schwarz and M. Van den Nest. Simulating quantum circuits with sparse output distributions, 2013. arXiv:1310.6749."
    },
    {
      "key": "39",
      "doi-asserted-by": "publisher",
      "unstructured": "V. Shchesnovich. Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal BosonSampling. Phys. Rev. A, 91: 063842, 2015. arXiv:1501.00850.",
      "DOI": "10.1103/PhysRevA.91.063842"
    },
    {
      "key": "40",
      "unstructured": "D. Shepherd. Binary matroids and quantum probability distributions, 2010. arXiv:1005.1744."
    },
    {
      "key": "41",
      "doi-asserted-by": "publisher",
      "unstructured": "D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proc. Roy. Soc. Ser. A, 465 (2105): 1413-1439, 2009. arXiv:0809.0847.",
      "DOI": "10.1098/rspa.2008.0443"
    },
    {
      "key": "42",
      "doi-asserted-by": "publisher",
      "unstructured": "D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26: 1474-1483, 1997.",
      "DOI": "10.1137/S0097539796298637"
    },
    {
      "key": "43",
      "doi-asserted-by": "publisher",
      "unstructured": "S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20 (5): 865-877, 1991.",
      "DOI": "10.1137/0220053"
    },
    {
      "key": "44",
      "doi-asserted-by": "publisher",
      "unstructured": "S. Virmani, S. Huelga, and M. Plenio. Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71: 042328, 2005. quant-ph/0408076.",
      "DOI": "10.1103/PhysRevA.71.042328"
    }
  ],
  "container-title": "Quantum",
  "original-title": [],
  "language": "en",
  "deposited": {
    "date-parts": [
      [
        2023,
        8,
        23
      ]
    ],
    "date-time": "2023-08-23T07:52:30Z",
    "timestamp": 1692777150000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://quantum-journal.org/papers/q-2017-04-25-8/"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2017,
        4,
        25
      ]
    ]
  },
  "references-count": 44,
  "URL": "http://dx.doi.org/10.22331/q-2017-04-25-8",
  "relation": {},
  "ISSN": [
    "2521-327X"
  ],
  "subject": [],
  "container-title-short": "Quantum",
  "published": {
    "date-parts": [
      [
        2017,
        4,
        25
      ]
    ]
  },
  "article-number": "8"
}