DOI: 10.1038/srep25598. Computational quantum-classical boundary of noisy commuting quantum circuits

Computational quantum-classical boundary of noisy commuting quantum circuits

10.1038/srep25598

Crossref journal-article

Springer Science and Business Media LLC

Scientific Reports (297)

Abstract

AbstractIt is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation in the quantum side, we utilize the postselection argument and crucially strengthen it by taking noise effect into account. Classical simulatability in the classical side is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.

Bibliography

Fujii, K., & Tamate, S. (2016). Computational quantum-classical boundary of noisy commuting quantum circuits. Scientific Reports, 6(1).

Authors 2

Keisuke Fujii (first)
Shuhei Tamate (additional)

References 59 Referenced 17

Zurek, W. H. Decoherence and the transition from quantum to classical–revisited. Physics Today 44, arXiv preprint quant-ph/0306072 (2003).
Zurek, W. H. Decoherence, einselection and the quantum origins of the classical. Rev. Mod. Phys. 75, 715 (2003). (10.1103/RevModPhys.75.715) / Rev. Mod. Phys. by WH Zurek (2003)
Bell, J. On the einsteinpodolskyrosen paradox. Physics 1, 195200 (1964). / Physics by J Bell (1964)
Bennett, C. H. et al. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys. Rev. Lett. 70, 1895 (1993). (10.1103/PhysRevLett.70.1895) / Phys. Rev. Lett. by CH Bennett (1993)
Ekert, A. K. Quantum cryptography based on bell’s theorem. Phys. Rev. Lett. 67, 661–663 (1991). (10.1103/PhysRevLett.67.661) / Phys. Rev. Lett. by AK Ekert (1991)
Gefter, A. Theoretical physics: Complexity on the horizon. Nature 509, 552 (2014). (10.1038/509552a) / Nature by A Gefter (2014)
Reichardt, B. W., Unger, F. & Vazirani, U. Classical command of quantum systems. Nature 496, 456–460 (2013). (10.1038/nature12035) / Nature by BW Reichardt (2013)
Johnson, M. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011). (10.1038/nature10012) / Nature by M Johnson (2011)
Rønnow, T. F. et al. Defining and detecting quantum speedup. Science 345, 420–424 (2014). (10.1126/science.1252319) / Science by TF Rønnow (2014)
Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10, 218–224 (2014). (10.1038/nphys2900) / Nat. Phys by S Boixo (2014)
Gottesman, D. Stabilizer codes and quantum error correction. Ph.D. thesis, California Institute of Technology (1997).
Valiant, L. G. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing 31, 1229–1254 (2002). (10.1137/S0097539700377025) / SIAM Journal on Computing by LG Valiant (2002)
Bravyi, S. & Raussendorf, R. Measurement-based quantum computation with the toric code states. Phy. Rev. A 76, 022304 (2007). (10.1103/PhysRevA.76.022304) / Phy. Rev. A by S Bravyi (2007)
Fujii, K. & Morimae, T. Quantum commuting circuits and complexity of ising partition functions. arXiv preprint arXiv:1311.2128 (2013).
Knill, E. & Laamme, R. Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672–5675 (1998). (10.1103/PhysRevLett.81.5672) / Phys. Rev. Lett. by E Knill (1998)
Morimae, T., Fujii, K. & Fitzsimons, J. F. Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014). (10.1103/PhysRevLett.112.130502) / Phys. Rev. Lett. by T Morimae (2014)
Fujii, K. et al. Impossibility of classically simulating one-clean-qubit computation. arXiv preprint arXiv:1409.6777 (2014).
Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. A 465, 1413–1439 (2009). (10.1098/rspa.2008.0443) / Proc. R. A by D Shepherd (2009)
Bremner, M. J., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. A 467, 459–472 (2011). (10.1098/rspa.2010.0301) / Proc. R. A by MJ Bremner (2011)
Nakata, Y. & Murao, M. Diagonal quantum circuits: Their computational power and applications. Eur. Phys. J. Plus 129, 1–14 (2014). (10.1140/epjp/i2014-14152-9) / Eur. Phys. J. Plus by Y Nakata (2014)
Aaronson, S. Guest column: Np-complete problems and physical reality. ACM Sigact News 36, 30–52 (2005). (10.1145/1052796.1052804) / ACM Sigact News by S Aaronson (2005)
Schönhage, A. On the power of random access machines (Springer, 1979). (10.1007/3-540-09510-1_42)
Verstraete, F. & Cirac, J. I. Valence-bond states for quantum computation. Phy. Rev. A 70, 060302 (2004). (10.1103/PhysRevA.70.060302) / Phy. Rev. A by F Verstraete (2004)
Raussendorf, R., Bravyi, S. & Harrington, J. Long-range quantum entanglement in noisy cluster states. Phys. Rev. A 71, 062313 (2005). (10.1103/PhysRevA.71.062313) / Phys. Rev. A by R Raussendorf (2005)
Barrett, S. D., Bartlett, S. D., Doherty, A. C., Jennings, D. & Rudolph, T. Transitions in the computational power of thermal states for measurement-based quantum computation. Phys. Rev. A 80, 062328 (2009). (10.1103/PhysRevA.80.062328) / Phys. Rev. A by SD Barrett (2009)
Hein, M. et al. Quantum computers, algorithms and chaos. In International School of Physics Enrico Fermi, vol. 162 (IOS, 2006).
Aaronson, S. Quantum computing, postselection and probabilistic polynomial-time. Proc. R. A 461, 3473–3482 (2005). (10.1098/rspa.2005.1546) / Proc. R. A by S Aaronson (2005)
Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. In Proc. 43rd STOC, 333–342 (ACM, 2011). (10.1145/1993636.1993682)
Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. arXiv preprint arXiv:1504.07999 (2015). (10.1103/PhysRevLett.117.080501)
Raussendorf, R., Harrington, J. & Goyal, K. A fault-tolerant one-way quantum computer. Ann. of phys. 321, 2242–2270 (2006). (10.1016/j.aop.2006.01.012) / Ann. of phys by R Raussendorf (2006)
Raussendorf, R., Harrington, J. & Goyal, K. Topological fault-tolerance in cluster state quantum computation. New J. Phys. 9, 199 (2007). (10.1088/1367-2630/9/6/199) / New J. Phys. by R Raussendorf (2007)
Fujii, K. Quantum computation with topological codes: from qubit to topological fault-tolerance. arXiv preprint arXiv:1504.01444 (2015). (10.1007/978-981-287-996-7)
Fujii, K. & Morimae, T. Topologically protected measurement-based quantum computation on the thermal state of a nearest-neighbor two-body hamiltonian with spin-3/2 particles. Phys. Rev. A 85, 010304 (2012). (10.1103/PhysRevA.85.010304) / Phys. Rev. A by K Fujii (2012)
Li, Y., Browne, D. E., Kwek, L. C., Raussendorf, R. & Wei, T.-C. Thermal states as universal resources for quantum computation with always-on interactions. Phys. Rev. Lett. 107, 060501 (2011). (10.1103/PhysRevLett.107.060501) / Phys. Rev. Lett. by Y Li (2011)
Morimae, T. & Fujii, K. Blind topological measurement-based quantum computation. Nat. Commun. 3, 1036 (2012). (10.1038/ncomms2043) / Nat. Commun. by T Morimae (2012)
Fujii, K., Nakata, Y., Ohzeki, M. & Murao, M. Measurement-based quantum computation on symmetry breaking thermal states. Phys. Rev. Lett. 110, 120502 (2013). (10.1103/PhysRevLett.110.120502) / Phys. Rev. Lett. by K Fujii (2013)
Dennis, E., Kitaev, A., Landahl, A. & Preskill, J. Topological quantum memory. J. of Math. Phys. 43, 4452–4505 (2002). (10.1063/1.1499754) / J. of Math. Phys by E Dennis (2002)
Knill, E. Quantum computing with realistically noisy devices. Nature 434, 39–44 (2005). (10.1038/nature03350) / Nature by E Knill (2005)
Knill, E. Scalable quantum computing in the presence of large detected-error rates. Phy. Rev. A 71, 042322 (2005). (10.1103/PhysRevA.71.042322) / Phy. Rev. A by E Knill (2005)
Fujii, K. & Yamamoto, K. Cluster-based architecture for fault-tolerant quantum computation. Phys. Rev. A 81, 042324 (2010). (10.1103/PhysRevA.81.042324) / Phys. Rev. A by K Fujii (2010)
Fujii, K. & Yamamoto, K. Topological one-way quantum computation on verified logical cluster states. Phys. Rev. A 82, 060301 (2010). (10.1103/PhysRevA.82.060301) / Phys. Rev. A by K Fujii (2010)
Aharonov, D., Kitaev, A. & Nisan, N. Quantum circuits with mixed states. In Proc. 30th STOC, 20–30 (ACM, 1998). (10.1145/276698.276708)
Aliferis, P. An introduction to reliable quantum computation. In Quantum Error Correction, 127–158 (Cambridge University Press, 2013).
Bravyi, S. & Kitaev, A. Universal quantum computation with ideal clifford gates and noisy ancillas. Phy. Rev. A 71, 022316 (2005). (10.1103/PhysRevA.71.022316) / Phy. Rev. A by S Bravyi (2005)
Reichardt, B. W. Quantum universality from magic states distillation applied to css codes. Quant. Inf. Proc. 4, 251–264 (2005). (10.1007/s11128-005-7654-8) / Quant. Inf. Proc by BW Reichardt (2005)
Aharonov, D., Jones, V. & Landau, Z. A polynomial quantum algorithm for approximating the jones polynomial. Algorithmica 55, 395–421 (2009). (10.1007/s00453-008-9168-0) / Algorithmica by D Aharonov (2009)
Aharonov, D. & Arad, I. The bqp-hardness of approximating the jones polynomial. arXiv preprint quant-ph/0605181 (2006).
Aharonov, D., Arad, I., Eban, E. & Landau, Z. Polynomial quantum algorithms for additive approximations of the potts model and other points of the tutte plane. arXiv preprint quant-ph/0702008 (2007).
Matsuo, A., Fujii, K. & Imoto, N. Quantum algorithm for an additive approximation of ising partition functions. Phys. Rev. A 90, 022304 (2014). (10.1103/PhysRevA.90.022304) / Phys. Rev. A by A Matsuo (2014)
Ni, X. & Nest, M. V. d. Commuting quantum circuits: efficient classical simulations versus hardness results. arXiv preprint arXiv:1204.4570 (2012).
Dür, W., Hein, M., Cirac, J. I. & Briegel, H.-J. Standard forms of noisy quantum operations via depolarization. Phys. Rev. A 72, 052326 (2005). (10.1103/PhysRevA.72.052326) / Phys. Rev. A by W Dür (2005)
Wootters, W. K. Entanglement of formation of an arbitrary state of two qubits. Phys. Rev. Lett. 80, 2245 (1998). (10.1103/PhysRevLett.80.2245) / Phys. Rev. Lett. by WK Wootters (1998)
Fitzsimons, J. F. & Kashefi, E. Unconditionally verifiable blind computation. arXiv preprint arXiv:1203.5217 (2012).
Howard, M., Wallman, J., Veitch, V. & Emerson, J. Contextuality supplies the /‘magic/’ for quantum computation. Nature 510, 351 (2014). (10.1038/nature13460) / Nature by M Howard (2014)
Knill, E., Laamme, R. & Milburn, G. J. A scheme for efficient quantum computation with linear optics. Nature 409, 46–52 (2001). (10.1038/35051009) / Nature by E Knill (2001)
Dawson, C. M., Haselgrove, H. L. & Nielsen, M. A. Noise thresholds for optical quantum computers. Phys. Rev. Lett. 96, 020501 (2006). (10.1103/PhysRevLett.96.020501) / Phys. Rev. Lett. by CM Dawson (2006)
Fujii, K. & Tokunaga, Y. Fault-tolerant topological one-way quantum computation with probabilistic two-qubit gates. Phys. Rev. Lett. 105, 250503 (2010). (10.1103/PhysRevLett.105.250503) / Phys. Rev. Lett. by K Fujii (2010)
Li, Y., Barrett, S. D., Stace, T. M. & Benjamin, S. C. Fault tolerant quantum computation with nondeterministic gates. Phys. Rev. Lett. 105, 250502 (2010). (10.1103/PhysRevLett.105.250502) / Phys. Rev. Lett. by Y Li (2010)
Rohde, P. P., Motes, K. R., Knott, P. & Munro, W. J. Will boson-sampling ever disprove the extended church-turing thesis? arXiv preprint arXiv:1401.2199 (2014).

Dates

Type	When
Created	9 years, 3 months ago (May 18, 2016, 5:07 a.m.)
Deposited	2 years, 7 months ago (Jan. 4, 2023, 10:52 a.m.)
Indexed	4 weeks ago (Aug. 6, 2025, 9:52 a.m.)
Issued	9 years, 3 months ago (May 18, 2016)
Published	9 years, 3 months ago (May 18, 2016)
Published Online	9 years, 3 months ago (May 18, 2016)

Funders 0

None

BibTeX

@article{Fujii_2016, title={Computational quantum-classical boundary of noisy commuting quantum circuits}, volume={6}, ISSN={2045-2322}, url={http://dx.doi.org/10.1038/srep25598}, DOI={10.1038/srep25598}, number={1}, journal={Scientific Reports}, publisher={Springer Science and Business Media LLC}, author={Fujii, Keisuke and Tamate, Shuhei}, year={2016}, month=may }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        6
      ]
    ],
    "date-time": "2025-08-06T13:52:04Z",
    "timestamp": 1754488324125
  },
  "reference-count": 59,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "1",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2016,
            5,
            18
          ]
        ],
        "date-time": "2016-05-18T00:00:00Z",
        "timestamp": 1463529600000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "https://creativecommons.org/licenses/by/4.0"
    },
    {
      "start": {
        "date-parts": [
          [
            2016,
            5,
            18
          ]
        ],
        "date-time": "2016-05-18T00:00:00Z",
        "timestamp": 1463529600000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://creativecommons.org/licenses/by/4.0"
    }
  ],
  "content-domain": {
    "domain": [
      "link.springer.com"
    ],
    "crossmark-restriction": false
  },
  "abstract": "<jats:title>Abstract</jats:title><jats:p>It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation in the quantum side, we utilize the postselection argument and crucially strengthen it by taking noise effect into account. Classical simulatability in the classical side is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.</jats:p>",
  "DOI": "10.1038/srep25598",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2016,
        5,
        18
      ]
    ],
    "date-time": "2016-05-18T09:07:55Z",
    "timestamp": 1463562475000
  },
  "update-policy": "http://dx.doi.org/10.1007/springer_crossmark_policy",
  "source": "Crossref",
  "is-referenced-by-count": 17,
  "title": "Computational quantum-classical boundary of noisy commuting quantum circuits",
  "prefix": "10.1038",
  "volume": "6",
  "author": [
    {
      "given": "Keisuke",
      "family": "Fujii",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Shuhei",
      "family": "Tamate",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2016,
        5,
        18
      ]
    ]
  },
  "reference": [
    {
      "key": "BFsrep25598_CR1",
      "unstructured": "Zurek, W. H. Decoherence and the transition from quantum to classical\u2013revisited. Physics Today 44, arXiv preprint quant-ph/0306072 (2003)."
    },
    {
      "key": "BFsrep25598_CR2",
      "doi-asserted-by": "publisher",
      "first-page": "715",
      "DOI": "10.1103/RevModPhys.75.715",
      "volume": "75",
      "author": "WH Zurek",
      "year": "2003",
      "unstructured": "Zurek, W. H. Decoherence, einselection and the quantum origins of the classical. Rev. Mod. Phys. 75, 715 (2003).",
      "journal-title": "Rev. Mod. Phys."
    },
    {
      "key": "BFsrep25598_CR3",
      "first-page": "195200",
      "volume": "1",
      "author": "J Bell",
      "year": "1964",
      "unstructured": "Bell, J. On the einsteinpodolskyrosen paradox. Physics 1, 195200 (1964).",
      "journal-title": "Physics"
    },
    {
      "key": "BFsrep25598_CR4",
      "doi-asserted-by": "publisher",
      "first-page": "1895",
      "DOI": "10.1103/PhysRevLett.70.1895",
      "volume": "70",
      "author": "CH Bennett",
      "year": "1993",
      "unstructured": "Bennett, C. H. et al. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys. Rev. Lett. 70, 1895 (1993).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR5",
      "doi-asserted-by": "publisher",
      "first-page": "661",
      "DOI": "10.1103/PhysRevLett.67.661",
      "volume": "67",
      "author": "AK Ekert",
      "year": "1991",
      "unstructured": "Ekert, A. K. Quantum cryptography based on bell\u2019s theorem. Phys. Rev. Lett. 67, 661\u2013663 (1991).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR6",
      "doi-asserted-by": "publisher",
      "first-page": "552",
      "DOI": "10.1038/509552a",
      "volume": "509",
      "author": "A Gefter",
      "year": "2014",
      "unstructured": "Gefter, A. Theoretical physics: Complexity on the horizon. Nature 509, 552 (2014).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR7",
      "doi-asserted-by": "publisher",
      "first-page": "456",
      "DOI": "10.1038/nature12035",
      "volume": "496",
      "author": "BW Reichardt",
      "year": "2013",
      "unstructured": "Reichardt, B. W., Unger, F. & Vazirani, U. Classical command of quantum systems. Nature 496, 456\u2013460 (2013).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR8",
      "doi-asserted-by": "publisher",
      "first-page": "194",
      "DOI": "10.1038/nature10012",
      "volume": "473",
      "author": "M Johnson",
      "year": "2011",
      "unstructured": "Johnson, M. et al. Quantum annealing with manufactured spins. Nature 473, 194\u2013198 (2011).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR9",
      "doi-asserted-by": "publisher",
      "first-page": "420",
      "DOI": "10.1126/science.1252319",
      "volume": "345",
      "author": "TF R\u00f8nnow",
      "year": "2014",
      "unstructured": "R\u00f8nnow, T. F. et al. Defining and detecting quantum speedup. Science 345, 420\u2013424 (2014).",
      "journal-title": "Science"
    },
    {
      "key": "BFsrep25598_CR10",
      "doi-asserted-by": "publisher",
      "first-page": "218",
      "DOI": "10.1038/nphys2900",
      "volume": "10",
      "author": "S Boixo",
      "year": "2014",
      "unstructured": "Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10, 218\u2013224 (2014).",
      "journal-title": "Nat. Phys"
    },
    {
      "key": "BFsrep25598_CR11",
      "unstructured": "Gottesman, D. Stabilizer codes and quantum error correction. Ph.D. thesis, California Institute of Technology (1997)."
    },
    {
      "key": "BFsrep25598_CR12",
      "doi-asserted-by": "publisher",
      "first-page": "1229",
      "DOI": "10.1137/S0097539700377025",
      "volume": "31",
      "author": "LG Valiant",
      "year": "2002",
      "unstructured": "Valiant, L. G. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing 31, 1229\u20131254 (2002).",
      "journal-title": "SIAM Journal on Computing"
    },
    {
      "key": "BFsrep25598_CR13",
      "doi-asserted-by": "publisher",
      "first-page": "022304",
      "DOI": "10.1103/PhysRevA.76.022304",
      "volume": "76",
      "author": "S Bravyi",
      "year": "2007",
      "unstructured": "Bravyi, S. & Raussendorf, R. Measurement-based quantum computation with the toric code states. Phy. Rev. A 76, 022304 (2007).",
      "journal-title": "Phy. Rev. A"
    },
    {
      "key": "BFsrep25598_CR14",
      "unstructured": "Fujii, K. & Morimae, T. Quantum commuting circuits and complexity of ising partition functions. arXiv preprint arXiv:1311.2128 (2013)."
    },
    {
      "key": "BFsrep25598_CR15",
      "doi-asserted-by": "publisher",
      "first-page": "5672",
      "DOI": "10.1103/PhysRevLett.81.5672",
      "volume": "81",
      "author": "E Knill",
      "year": "1998",
      "unstructured": "Knill, E. & Laamme, R. Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672\u20135675 (1998).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR16",
      "doi-asserted-by": "publisher",
      "first-page": "130502",
      "DOI": "10.1103/PhysRevLett.112.130502",
      "volume": "112",
      "author": "T Morimae",
      "year": "2014",
      "unstructured": "Morimae, T., Fujii, K. & Fitzsimons, J. F. Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR17",
      "unstructured": "Fujii, K. et al. Impossibility of classically simulating one-clean-qubit computation. arXiv preprint arXiv:1409.6777 (2014)."
    },
    {
      "key": "BFsrep25598_CR18",
      "doi-asserted-by": "publisher",
      "first-page": "1413",
      "DOI": "10.1098/rspa.2008.0443",
      "volume": "465",
      "author": "D Shepherd",
      "year": "2009",
      "unstructured": "Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. A 465, 1413\u20131439 (2009).",
      "journal-title": "Proc. R. A"
    },
    {
      "key": "BFsrep25598_CR19",
      "doi-asserted-by": "publisher",
      "first-page": "459",
      "DOI": "10.1098/rspa.2010.0301",
      "volume": "467",
      "author": "MJ Bremner",
      "year": "2011",
      "unstructured": "Bremner, M. J., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. A 467, 459\u2013472 (2011).",
      "journal-title": "Proc. R. A"
    },
    {
      "key": "BFsrep25598_CR20",
      "doi-asserted-by": "publisher",
      "first-page": "1",
      "DOI": "10.1140/epjp/i2014-14152-9",
      "volume": "129",
      "author": "Y Nakata",
      "year": "2014",
      "unstructured": "Nakata, Y. & Murao, M. Diagonal quantum circuits: Their computational power and applications. Eur. Phys. J. Plus 129, 1\u201314 (2014).",
      "journal-title": "Eur. Phys. J. Plus"
    },
    {
      "key": "BFsrep25598_CR21",
      "doi-asserted-by": "publisher",
      "first-page": "30",
      "DOI": "10.1145/1052796.1052804",
      "volume": "36",
      "author": "S Aaronson",
      "year": "2005",
      "unstructured": "Aaronson, S. Guest column: Np-complete problems and physical reality. ACM Sigact News 36, 30\u201352 (2005).",
      "journal-title": "ACM Sigact News"
    },
    {
      "key": "BFsrep25598_CR22",
      "doi-asserted-by": "crossref",
      "unstructured": "Sch\u00f6nhage, A. On the power of random access machines (Springer, 1979).",
      "DOI": "10.1007/3-540-09510-1_42"
    },
    {
      "key": "BFsrep25598_CR23",
      "doi-asserted-by": "publisher",
      "first-page": "060302",
      "DOI": "10.1103/PhysRevA.70.060302",
      "volume": "70",
      "author": "F Verstraete",
      "year": "2004",
      "unstructured": "Verstraete, F. & Cirac, J. I. Valence-bond states for quantum computation. Phy. Rev. A 70, 060302 (2004).",
      "journal-title": "Phy. Rev. A"
    },
    {
      "key": "BFsrep25598_CR24",
      "doi-asserted-by": "publisher",
      "first-page": "062313",
      "DOI": "10.1103/PhysRevA.71.062313",
      "volume": "71",
      "author": "R Raussendorf",
      "year": "2005",
      "unstructured": "Raussendorf, R., Bravyi, S. & Harrington, J. Long-range quantum entanglement in noisy cluster states. Phys. Rev. A 71, 062313 (2005).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR25",
      "doi-asserted-by": "publisher",
      "first-page": "062328",
      "DOI": "10.1103/PhysRevA.80.062328",
      "volume": "80",
      "author": "SD Barrett",
      "year": "2009",
      "unstructured": "Barrett, S. D., Bartlett, S. D., Doherty, A. C., Jennings, D. & Rudolph, T. Transitions in the computational power of thermal states for measurement-based quantum computation. Phys. Rev. A 80, 062328 (2009).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR26",
      "unstructured": "Hein, M. et al. Quantum computers, algorithms and chaos. In International School of Physics Enrico Fermi, vol. 162 (IOS, 2006)."
    },
    {
      "key": "BFsrep25598_CR27",
      "doi-asserted-by": "publisher",
      "first-page": "3473",
      "DOI": "10.1098/rspa.2005.1546",
      "volume": "461",
      "author": "S Aaronson",
      "year": "2005",
      "unstructured": "Aaronson, S. Quantum computing, postselection and probabilistic polynomial-time. Proc. R. A 461, 3473\u20133482 (2005).",
      "journal-title": "Proc. R. A"
    },
    {
      "key": "BFsrep25598_CR28",
      "doi-asserted-by": "crossref",
      "unstructured": "Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. In Proc. 43rd STOC, 333\u2013342 (ACM, 2011).",
      "DOI": "10.1145/1993636.1993682"
    },
    {
      "key": "BFsrep25598_CR29",
      "doi-asserted-by": "crossref",
      "unstructured": "Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. arXiv preprint arXiv:1504.07999 (2015).",
      "DOI": "10.1103/PhysRevLett.117.080501"
    },
    {
      "key": "BFsrep25598_CR30",
      "doi-asserted-by": "publisher",
      "first-page": "2242",
      "DOI": "10.1016/j.aop.2006.01.012",
      "volume": "321",
      "author": "R Raussendorf",
      "year": "2006",
      "unstructured": "Raussendorf, R., Harrington, J. & Goyal, K. A fault-tolerant one-way quantum computer. Ann. of phys. 321, 2242\u20132270 (2006).",
      "journal-title": "Ann. of phys"
    },
    {
      "key": "BFsrep25598_CR31",
      "doi-asserted-by": "publisher",
      "first-page": "199",
      "DOI": "10.1088/1367-2630/9/6/199",
      "volume": "9",
      "author": "R Raussendorf",
      "year": "2007",
      "unstructured": "Raussendorf, R., Harrington, J. & Goyal, K. Topological fault-tolerance in cluster state quantum computation. New J. Phys. 9, 199 (2007).",
      "journal-title": "New J. Phys."
    },
    {
      "key": "BFsrep25598_CR32",
      "doi-asserted-by": "crossref",
      "unstructured": "Fujii, K. Quantum computation with topological codes: from qubit to topological fault-tolerance. arXiv preprint arXiv:1504.01444 (2015).",
      "DOI": "10.1007/978-981-287-996-7"
    },
    {
      "key": "BFsrep25598_CR33",
      "doi-asserted-by": "publisher",
      "first-page": "010304",
      "DOI": "10.1103/PhysRevA.85.010304",
      "volume": "85",
      "author": "K Fujii",
      "year": "2012",
      "unstructured": "Fujii, K. & Morimae, T. Topologically protected measurement-based quantum computation on the thermal state of a nearest-neighbor two-body hamiltonian with spin-3/2 particles. Phys. Rev. A 85, 010304 (2012).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR34",
      "doi-asserted-by": "publisher",
      "first-page": "060501",
      "DOI": "10.1103/PhysRevLett.107.060501",
      "volume": "107",
      "author": "Y Li",
      "year": "2011",
      "unstructured": "Li, Y., Browne, D. E., Kwek, L. C., Raussendorf, R. & Wei, T.-C. Thermal states as universal resources for quantum computation with always-on interactions. Phys. Rev. Lett. 107, 060501 (2011).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR35",
      "doi-asserted-by": "publisher",
      "first-page": "1036",
      "DOI": "10.1038/ncomms2043",
      "volume": "3",
      "author": "T Morimae",
      "year": "2012",
      "unstructured": "Morimae, T. & Fujii, K. Blind topological measurement-based quantum computation. Nat. Commun. 3, 1036 (2012).",
      "journal-title": "Nat. Commun."
    },
    {
      "key": "BFsrep25598_CR36",
      "doi-asserted-by": "publisher",
      "first-page": "120502",
      "DOI": "10.1103/PhysRevLett.110.120502",
      "volume": "110",
      "author": "K Fujii",
      "year": "2013",
      "unstructured": "Fujii, K., Nakata, Y., Ohzeki, M. & Murao, M. Measurement-based quantum computation on symmetry breaking thermal states. Phys. Rev. Lett. 110, 120502 (2013).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR37",
      "doi-asserted-by": "publisher",
      "first-page": "4452",
      "DOI": "10.1063/1.1499754",
      "volume": "43",
      "author": "E Dennis",
      "year": "2002",
      "unstructured": "Dennis, E., Kitaev, A., Landahl, A. & Preskill, J. Topological quantum memory. J. of Math. Phys. 43, 4452\u20134505 (2002).",
      "journal-title": "J. of Math. Phys"
    },
    {
      "key": "BFsrep25598_CR38",
      "doi-asserted-by": "publisher",
      "first-page": "39",
      "DOI": "10.1038/nature03350",
      "volume": "434",
      "author": "E Knill",
      "year": "2005",
      "unstructured": "Knill, E. Quantum computing with realistically noisy devices. Nature 434, 39\u201344 (2005).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR39",
      "doi-asserted-by": "publisher",
      "first-page": "042322",
      "DOI": "10.1103/PhysRevA.71.042322",
      "volume": "71",
      "author": "E Knill",
      "year": "2005",
      "unstructured": "Knill, E. Scalable quantum computing in the presence of large detected-error rates. Phy. Rev. A 71, 042322 (2005).",
      "journal-title": "Phy. Rev. A"
    },
    {
      "key": "BFsrep25598_CR40",
      "doi-asserted-by": "publisher",
      "first-page": "042324",
      "DOI": "10.1103/PhysRevA.81.042324",
      "volume": "81",
      "author": "K Fujii",
      "year": "2010",
      "unstructured": "Fujii, K. & Yamamoto, K. Cluster-based architecture for fault-tolerant quantum computation. Phys. Rev. A 81, 042324 (2010).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR41",
      "doi-asserted-by": "publisher",
      "first-page": "060301",
      "DOI": "10.1103/PhysRevA.82.060301",
      "volume": "82",
      "author": "K Fujii",
      "year": "2010",
      "unstructured": "Fujii, K. & Yamamoto, K. Topological one-way quantum computation on verified logical cluster states. Phys. Rev. A 82, 060301 (2010).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR42",
      "doi-asserted-by": "crossref",
      "unstructured": "Aharonov, D., Kitaev, A. & Nisan, N. Quantum circuits with mixed states. In Proc. 30th STOC, 20\u201330 (ACM, 1998).",
      "DOI": "10.1145/276698.276708"
    },
    {
      "key": "BFsrep25598_CR43",
      "unstructured": "Aliferis, P. An introduction to reliable quantum computation. In Quantum Error Correction, 127\u2013158 (Cambridge University Press, 2013)."
    },
    {
      "key": "BFsrep25598_CR44",
      "doi-asserted-by": "publisher",
      "first-page": "022316",
      "DOI": "10.1103/PhysRevA.71.022316",
      "volume": "71",
      "author": "S Bravyi",
      "year": "2005",
      "unstructured": "Bravyi, S. & Kitaev, A. Universal quantum computation with ideal clifford gates and noisy ancillas. Phy. Rev. A 71, 022316 (2005).",
      "journal-title": "Phy. Rev. A"
    },
    {
      "key": "BFsrep25598_CR45",
      "doi-asserted-by": "publisher",
      "first-page": "251",
      "DOI": "10.1007/s11128-005-7654-8",
      "volume": "4",
      "author": "BW Reichardt",
      "year": "2005",
      "unstructured": "Reichardt, B. W. Quantum universality from magic states distillation applied to css codes. Quant. Inf. Proc. 4, 251\u2013264 (2005).",
      "journal-title": "Quant. Inf. Proc"
    },
    {
      "key": "BFsrep25598_CR46",
      "doi-asserted-by": "publisher",
      "first-page": "395",
      "DOI": "10.1007/s00453-008-9168-0",
      "volume": "55",
      "author": "D Aharonov",
      "year": "2009",
      "unstructured": "Aharonov, D., Jones, V. & Landau, Z. A polynomial quantum algorithm for approximating the jones polynomial. Algorithmica 55, 395\u2013421 (2009).",
      "journal-title": "Algorithmica"
    },
    {
      "key": "BFsrep25598_CR47",
      "unstructured": "Aharonov, D. & Arad, I. The bqp-hardness of approximating the jones polynomial. arXiv preprint quant-ph/0605181 (2006)."
    },
    {
      "key": "BFsrep25598_CR48",
      "unstructured": "Aharonov, D., Arad, I., Eban, E. & Landau, Z. Polynomial quantum algorithms for additive approximations of the potts model and other points of the tutte plane. arXiv preprint quant-ph/0702008 (2007)."
    },
    {
      "key": "BFsrep25598_CR49",
      "doi-asserted-by": "publisher",
      "first-page": "022304",
      "DOI": "10.1103/PhysRevA.90.022304",
      "volume": "90",
      "author": "A Matsuo",
      "year": "2014",
      "unstructured": "Matsuo, A., Fujii, K. & Imoto, N. Quantum algorithm for an additive approximation of ising partition functions. Phys. Rev. A 90, 022304 (2014).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR50",
      "unstructured": "Ni, X. & Nest, M. V. d. Commuting quantum circuits: efficient classical simulations versus hardness results. arXiv preprint arXiv:1204.4570 (2012)."
    },
    {
      "key": "BFsrep25598_CR51",
      "doi-asserted-by": "publisher",
      "first-page": "052326",
      "DOI": "10.1103/PhysRevA.72.052326",
      "volume": "72",
      "author": "W D\u00fcr",
      "year": "2005",
      "unstructured": "D\u00fcr, W., Hein, M., Cirac, J. I. & Briegel, H.-J. Standard forms of noisy quantum operations via depolarization. Phys. Rev. A 72, 052326 (2005).",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "BFsrep25598_CR52",
      "doi-asserted-by": "publisher",
      "first-page": "2245",
      "DOI": "10.1103/PhysRevLett.80.2245",
      "volume": "80",
      "author": "WK Wootters",
      "year": "1998",
      "unstructured": "Wootters, W. K. Entanglement of formation of an arbitrary state of two qubits. Phys. Rev. Lett. 80, 2245 (1998).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR53",
      "unstructured": "Fitzsimons, J. F. & Kashefi, E. Unconditionally verifiable blind computation. arXiv preprint arXiv:1203.5217 (2012)."
    },
    {
      "key": "BFsrep25598_CR54",
      "doi-asserted-by": "publisher",
      "first-page": "351",
      "DOI": "10.1038/nature13460",
      "volume": "510",
      "author": "M Howard",
      "year": "2014",
      "unstructured": "Howard, M., Wallman, J., Veitch, V. & Emerson, J. Contextuality supplies the /\u2018magic/\u2019 for quantum computation. Nature 510, 351 (2014).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR55",
      "doi-asserted-by": "publisher",
      "first-page": "46",
      "DOI": "10.1038/35051009",
      "volume": "409",
      "author": "E Knill",
      "year": "2001",
      "unstructured": "Knill, E., Laamme, R. & Milburn, G. J. A scheme for efficient quantum computation with linear optics. Nature 409, 46\u201352 (2001).",
      "journal-title": "Nature"
    },
    {
      "key": "BFsrep25598_CR56",
      "doi-asserted-by": "publisher",
      "first-page": "020501",
      "DOI": "10.1103/PhysRevLett.96.020501",
      "volume": "96",
      "author": "CM Dawson",
      "year": "2006",
      "unstructured": "Dawson, C. M., Haselgrove, H. L. & Nielsen, M. A. Noise thresholds for optical quantum computers. Phys. Rev. Lett. 96, 020501 (2006).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR57",
      "doi-asserted-by": "publisher",
      "first-page": "250503",
      "DOI": "10.1103/PhysRevLett.105.250503",
      "volume": "105",
      "author": "K Fujii",
      "year": "2010",
      "unstructured": "Fujii, K. & Tokunaga, Y. Fault-tolerant topological one-way quantum computation with probabilistic two-qubit gates. Phys. Rev. Lett. 105, 250503 (2010).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR58",
      "doi-asserted-by": "publisher",
      "first-page": "250502",
      "DOI": "10.1103/PhysRevLett.105.250502",
      "volume": "105",
      "author": "Y Li",
      "year": "2010",
      "unstructured": "Li, Y., Barrett, S. D., Stace, T. M. & Benjamin, S. C. Fault tolerant quantum computation with nondeterministic gates. Phys. Rev. Lett. 105, 250502 (2010).",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "BFsrep25598_CR59",
      "unstructured": "Rohde, P. P., Motes, K. R., Knott, P. & Munro, W. J. Will boson-sampling ever disprove the extended church-turing thesis? arXiv preprint arXiv:1401.2199 (2014)."
    }
  ],
  "container-title": "Scientific Reports",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://www.nature.com/articles/srep25598",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://www.nature.com/articles/srep25598.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://www.nature.com/articles/srep25598.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2023,
        1,
        4
      ]
    ],
    "date-time": "2023-01-04T15:52:02Z",
    "timestamp": 1672847522000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://www.nature.com/articles/srep25598"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2016,
        5,
        18
      ]
    ]
  },
  "references-count": 59,
  "journal-issue": {
    "issue": "1",
    "published-online": {
      "date-parts": [
        [
          2016,
          9,
          19
        ]
      ]
    }
  },
  "alternative-id": [
    "BFsrep25598"
  ],
  "URL": "http://dx.doi.org/10.1038/srep25598",
  "relation": {},
  "ISSN": [
    "2045-2322"
  ],
  "subject": [],
  "container-title-short": "Sci Rep",
  "published": {
    "date-parts": [
      [
        2016,
        5,
        18
      ]
    ]
  },
  "assertion": [
    {
      "value": "18 December 2015",
      "order": 1,
      "name": "received",
      "label": "Received",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "20 April 2016",
      "order": 2,
      "name": "accepted",
      "label": "Accepted",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "18 May 2016",
      "order": 3,
      "name": "first_online",
      "label": "First Online",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "The authors declare no competing financial interests.",
      "order": 1,
      "name": "Ethics",
      "group": {
        "name": "EthicsHeading",
        "label": "Competing interests"
      }
    }
  ],
  "article-number": "25598"
}