1Department of Mathematics, Brunel University London, Kingston Ln, Uxbridge, UB8 3PH, United Kingdom
2Phytoform Labs Ltd., Lawes Open Innovation Hub, West Common, Harpenden, Hertfordshire, England, AL5 2JQ, United Kingdom
3Department of Physics and Astronomy, Dartmouth College, Hanover, New Hampshire, 03755, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We provide new examples of pure entangled systems related to cluster state quantum computation that can be efficiently simulated classically. In cluster state quantum computation input qubits are initialised in the `equator’ of the Bloch sphere, $CZ$ gates are applied, and finally the qubits are measured adaptively using $Z$ measurements or measurements of $cos(theta)X + sin(theta)Y$ operators. We consider what happens when the initialisation step is modified, and show that for lattices of finite degree $D$, there is a constant $lambda approx 2.06$ such that if the qubits are prepared in a state that is within $lambda^{-D}$ in trace distance of a state that is diagonal in the computational basis, then the system can be efficiently simulated classically in the sense of sampling from the output distribution within a desired total variation distance. In the square lattice with $D=4$ for instance, $lambda^{-D} approx 0.056$. We develop a coarse grained version of the argument which increases the size of the classically efficient region. In the case of the square lattice of qubits, the size of the classically simulatable region increases in size to at least around $approx 0.070$, and in fact probably increases to around $approx 0.1$. The results generalise to a broader family of systems, including qudit systems where the interaction is diagonal in the computational basis and the measurements are either in the computational basis or unbiased to it. Potential readers who only want the short version can get much of the intuition from figures 1 to 3.
Featured image: This image illustrates a central concept exploited in the work. In standard quantum theory, a state of multiple particles is entangled if it cannot be considered to be a random mixture of local states of the individual particles. In standard quantum theory individual qubits have local state spaces corresponding to the Bloch sphere. In our work we allow the local state spaces to correspond to cylinders, not spheres. This enables us to describe some quantum entangled states as non-entangled ones in a cylindrical theory, and this is exploited by the classical simulation algorithm. The cylindrical theory that we use can lead to negative probabilities. However, for some systems this does not arise, and those systems can be efficiently simulated by our method.
[embedded content]
Popular summary
However, in spite of its central importance, any answers we have to this question are far from being complete.
In this work we make progress on this problem by providing a new way to classically simulate a family of pure entangled quantum systems. The family is non-trivial in that that every state within it is pure (i.e. isolated from any environment) and multi-party entangled. For one set of parameters the family contains ideal cluster state quantum computation. However, for other parameter regimes the simulation method is efficient. The fact that these systems can be efficiently simulated classically was previously unknown. Moreover, the method provides a type of local-hidden variable model for some measurements on otherwise pure entangled quantum systems.
The method has interesting connections to the foundations of physics. It works by describing the systems as non-entangled states in a kind of non-quantum theory. In this theory the constituent particles are not described by the usual qubit Bloch sphere, but a state space that is more akin to a cylinder. However, for some of the input states in the family this non-quantum theory breaks down, yielding negative probabilities. Where it does not break down is exactly where it provides an efficient classical simulation.
The method is amenable to a certain form of coarse graining, where particles are grouped into blocks and treated as individual particles. This increases significantly the set of states that can be efficiently simulated classically.
The method can also be generalised to a wider range of systems where particles are first interacted by finite depth commuting circuits and then measured in particular bases.
► BibTeX data
► References
[1] J. Preskill, Quantum computing 40 years later. arXiv:2106.10522 [quant-ph]. DOI: 10.48550/arXiv.2106.10522.
https://doi.org/10.48550/arXiv.2106.10522
arXiv:2106.10522
[2] R. Raussendorf and H.J. Briegel, A One-Way Quantum Computer. Phys. Rev. Lett. 86, 5188 (2001). DOI: 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188
[3] A. Harrow and M. Nielsen, Robustness of quantum gates in the presence of noise. Phys. Rev. A 68, 012308 (2003). DOI: 10.1103/PhysRevA.68.012308.
https://doi.org/10.1103/PhysRevA.68.012308
[4] D. Aharonov and M. Ben-Or, Polynomial simulations of decohered quantum computers. 37th Annual Symposium on Foundations of Computer Science (FOCS) pp 46–55, (1996). DOI: 10.1109/SFCS.1996.548463.
https://doi.org/10.1109/SFCS.1996.548463
[5] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits. Phys. Rev. A 70 (5): 052328, (2004). DOI: 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328
[6] E. Knill, Fault-Tolerant Postselected Quantum Computation: Schemes. arXiv:quant-ph/0402171. DOI: 10.48550/arXiv.quant-ph/0402171.
https://doi.org/10.48550/arXiv.quant-ph/0402171
arXiv:quant-ph/0402171
[7] S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316, (2005). DOI: 10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316
[8] H. Barnum, E. Knill, G. Ortiz, and L. Viola. Generalizations of entanglement based on coherent states and convex sets. Phys. Rev. A 68, 032308 (2003). DOI: 10.1103/PhysRevA.68.032308.
https://doi.org/10.1103/PhysRevA.68.032308
[9] H. Barnum, E. Knill, G. Ortiz, R. Somma, and L. Viola. A Subsystem-Independent Generalization of Entanglement. Phys. Rev. Lett. 92, 107902 (2004). DOI: 10.1103/PhysRevLett.92.107902.
https://doi.org/10.1103/PhysRevLett.92.107902
[10] A. Klyachko, Coherent States, Entanglement, and Geometric Invariant Theory,arXiv:quant-ph/0206012, (2002). DOI: 10.48550/arXiv.quant-ph/0206012.
https://doi.org/10.48550/arXiv.quant-ph/0206012
arXiv:quant-ph/0206012
[11] K. S. Gibbons, M. J. Hoffman, and W. K. Wootters. Discrete phase space based on finite fields. Phys. Rev. A 70, 062101 (2004). DOI: 10.1103/PhysRevA.70.062101.
https://doi.org/10.1103/PhysRevA.70.062101
[12] D. Gross. Hudson’s theorem for finite-dimensional quantum systems. J. Math. Phys., 47(12):122107 (2006). DOI: 10.1063/1.2393152.
https://doi.org/10.1063/1.2393152
[13] J. Barrett, Information processing in generalized probabilistic theories. Phys. Rev. A 75, 032304 (2007). DOI: 10.1103/PhysRevA.75.032304.
https://doi.org/10.1103/PhysRevA.75.032304
[14] L. Hardy, Quantum Theory From Five Reasonable Axioms. quant-ph/0101012 , (2001). DOI: 10.48550/arXiv.quant-ph/0101012.
https://doi.org/10.48550/arXiv.quant-ph/0101012
arXiv:quant-ph/0101012
[15] A. S. Holevo, “Probabilistic and Statistical Aspects of Quantum Theory”, North Holland (1982). DOI: 10.1007/978-88-7642-378-9.
https://doi.org/10.1007/978-88-7642-378-9
[16] S. Popescu and D. Rohrlich, Quantum nonlocality as an axiom. Foundations of Physics, 24, 379 (1994). DOI: 10.1007/BF02058098.
https://doi.org/10.1007/BF02058098
[17] Barrett, J., de Beaudrap, N., Hoban, M.J., and Lee, C., The computational landscape of general physical theories. NPJ Quantum Inf 5, 41 (2019). DOI: 10.1038/s41534-019-0156-9.
https://doi.org/10.1038/s41534-019-0156-9
[18] N. Ratanje and S. Virmani, Generalized state spaces and nonlocality in fault-tolerant quantum-computing schemes. Phys. Rev. A 83 032309 (2011). DOI: 10.1103/PhysRevA.83.032309.
https://doi.org/10.1103/PhysRevA.83.032309
[19] N. Ratanje and S. Virmani, Exploiting non-quantum entanglement to widen applicability of limited-entanglement classical simulations of quantum systems. arXiv:1201.0613v1. DOI: 10.48550/arXiv.1201.0613.
https://doi.org/10.48550/arXiv.1201.0613
arXiv:1201.0613v1
[20] H. Anwar, S Jevtic, O. Rudolph, and S. Virmani, Families of pure PEPS with efficiently simulatable local hidden variable models for most measurements. arXiv:1412.3780v2. DOI: 10.48550/arXiv.1412.3780.
https://doi.org/10.48550/arXiv.1412.3780
arXiv:1412.3780v2
[21] H. Anwar, S. Jevtic, O. Rudolph, and S. Virmani. Smallest disentangling state spaces for general entangled bipartite quantum states. New J. Phys. 17, 093047 (2015). DOI: 10.1088/1367-2630/17/9/093047.
https://doi.org/10.1088/1367-2630/17/9/093047
[22] H. Anwar, S. Jevtic, O. Rudolph, and S. Virmani. Generalised versions of separable decompositions applicable to bipartite entangled quantum states. New J. Phys. 21, 093031 (2019). DOI: 10.1088/1367-2630/ab3adc.
https://doi.org/10.1088/1367-2630/ab3adc
[23] O. Rudolph, A separability criterion for density operators, J. Phys. A: Math. Gen. 33 3951 (2000). DOI: 10.1088/0305-4470/33/21/308; O. Rudolph, A new class of entanglement measures, J. Math. Phys. 42 5306 (2001). DOI: 10.1088/0305-4470/33/21/308.
https://doi.org/10.1088/0305-4470/33/21/308
[24] F. Verstraete and J.I. Cirac, Valence-bond states for quantum computation. Phys. Rev. A 70, 060302(R) (2004). DOI: 10.1103/PhysRevA.70.060302.
https://doi.org/10.1103/PhysRevA.70.060302
[25] R F Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40 4277 (1989). DOI: 10.1103/PhysRevA.40.4277.
https://doi.org/10.1103/PhysRevA.40.4277
[26] Avis, D. (2010). Polyhedral Computation: Lecture 2. Kyoto University. Retrieved from http://www.lab2.kuis.kyoto-u.ac.jp/ avis/courses/pc/2010/notes/lec2.pdf.
http://www.lab2.kuis.kyoto-u.ac.jp/~avis/courses/pc/2010/notes/lec2.pdf
[27] Barrett, S., Bartlett, S., Doherty, A., Jennings, D. & Rudolph, T. Transitions in the computational power of thermal states for measurement-based quantum computation. Physical Review A. 80, 062328 (2009). DOI: 10.1103/PhysRevA.80.062328.
https://doi.org/10.1103/PhysRevA.80.062328
[28] Browne, D., Elliott, M., Flammia, S., Merkel, S., Miyake, A. & Short, A. Phase transition of computational power in the resource states for one-way quantum computation. New Journal Of Physics. 10, 023010 (2008). DOI: 10.1088/1367-2630/10/2/023010.
https://doi.org/10.1088/1367-2630/10/2/023010
[29] A. Peres. Separability Criterion for Density Matrices. Phys. Rev. Lett. 77 (8): 1413 (1996). DOI: 10.1103/PhysRevLett.77.1413.
https://doi.org/10.1103/PhysRevLett.77.1413
[30] M. Horodecki, P. Horodecki, and R. Horodecki. Separability of mixed states: necessary and sufficient conditions. Phys. Lett. A. 223 (1–2): 1–8. (1996). DOI: 10.1016/S0375-9601(96)00706-2.
https://doi.org/10.1016/S0375-9601(96)00706-2
[31] Mora, C., Piani, M., Miyake, A., Van den Nest, M., Dür, W. & Briegel, H. Universal resources for approximate and stochastic measurement-based quantum computation. Physical Review A. 81, 042315 (2010). DOI: 10.1103/PhysRevA.81.042315.
https://doi.org/10.1103/PhysRevA.81.042315
[32] B. Terhal and D. DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quant. Inf. Comp. Vol. 4 (No. 2), pages 134–145 (2004). DOI: 10.26421/QIC4.2-5.
https://doi.org/10.26421/QIC4.2-5
[33] Harrow, A. & Montanaro, A. Quantum computational supremacy. Nature. 549, 203-209 (2017). DOI: 10.1038/nature23458.
https://doi.org/10.1038/nature23458
[34] Bremner, M., Jozsa, R. & Shepherd, D. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 467, 459-472 (2011). DOI: 10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301
[35] Bremner, M., Montanaro, A. & Shepherd, D. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters. 117, 080501 (2016). DOI: 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501
[36] Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Proc. 32 Comput. Complex. Conf., CCC ’17 (2017). DOI: 10.4230/LIPIcs.CCC.2017.22.
https://doi.org/10.4230/LIPIcs.CCC.2017.22
[37] Bremner, M., Montanaro, A. & Shepherd, D. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum. 1 pp. 8 (2017). DOI: 10.22331/q-2017-04-25-8.
https://doi.org/10.22331/q-2017-04-25-8
[38] Miller, J., Sanders, S. & Miyake, A. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Physical Review A. 96, 062320 (2017). DOI: 10.1103/PhysRevA.96.062320.
https://doi.org/10.1103/PhysRevA.96.062320
[39] Gao, X., Wang, S. & Duan, L. Quantum supremacy for simulating a translation-invariant Ising spin model. Physical Review Letters. 118, 040502 (2017). DOI: 10.1103/PhysRevLett.118.040502.
https://doi.org/10.1103/PhysRevLett.118.040502
[40] Yoganathan, M., Jozsa, R. & Strelchuk, S. Quantum advantage of unitary Clifford circuits with magic state inputs. Proceedings Of The Royal Society A. 475, 20180427 (2019). DOI: 10.1098/rspa.2018.0427.
https://doi.org/10.1098/rspa.2018.0427
[41] Haferkamp, J., Hangleiter, D., Bouland, A., Fefferman, B., Eisert, J. & Bermejo-Vega, J. Closing gaps of a quantum advantage with short-time Hamiltonian dynamics. Physical Review Letters. 125, 250501 (2020). DOI: 10.1103/PhysRevLett.125.250501.
https://doi.org/10.1103/PhysRevLett.125.250501
[42] R. Jozsa and N. Linden, On the role of entanglement in quantum-computational speed-up. Proc. Roy. Soc. A, 459 2036 (2003). DOI: 10.1098/rspa.2002.1097.
https://doi.org/10.1098/rspa.2002.1097
[43] M. Yoganathan and C. Cade, The one clean qubit model without entanglement is classically simulable. arXiv:1907.08224v1. DOI: 10.48550/arXiv.1907.08224.
https://doi.org/10.48550/arXiv.1907.08224
arXiv:1907.08224v1
[44] G. Vidal, Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett. 91 147902, (2003). DOI: 10.1103/PhysRevLett.91.147902.
https://doi.org/10.1103/PhysRevLett.91.147902
[45] M. A. Nielsen, Cluster-state quantum computation. Rep. Math. Phys. 57 147–61 (2006). DOI: 10.1016/S0034-4877(06)80014-5.
https://doi.org/10.1016/S0034-4877(06)80014-5
[46] N. Yoran and A. J. Short, Classical Simulation of Limited-Width Cluster-State Quantum Computation. Phys. Rev. Lett. 96, 170503 (2006). DOI: 10.1103/PhysRevLett.96.170503.
https://doi.org/10.1103/PhysRevLett.96.170503
[47] I. L. Markov and Y. Shi, Simulating Quantum Computation by Contracting Tensor Networks. SIAM Journal on Computing, 38(3):963-981, (2008). DOI: 10.1137/050644756.
https://doi.org/10.1137/050644756
[48] S. Ghosh, A. Deshpande, D. Hangleiter, Alexey V. Gorshkov, and B. Fefferman, Complexity Phase Transitions Generated by Entanglement. Phys. Rev. Lett. 131, 030601 (2023). DOI: 10.1103/PhysRevLett.131.030601.
https://doi.org/10.1103/PhysRevLett.131.030601
[49] S Bravyi, D Gosset, R König, and M Tomamichel, Quantum advantage with noisy shallow circuits in 3D. Nature Physics 16 (10), 1040-1045, 2020. DOI: 10.1038/s41567-020-0948-z.
https://doi.org/10.1038/s41567-020-0948-z
[50] Jozsa, R. & Miyake, A. Matchgates and classical simulation of quantum circuits. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 464, 3089-3106 (2008). DOI: 10.1098/rspa.2008.0189.
https://doi.org/10.1098/rspa.2008.0189
[51] Jozsa, R. & Van den Nest, M. Classical simulation complexity of extended Clifford circuits. Quantum Info.Comput., 14, pp. 633–648, (2014). DOI: 10.26421/QIC14.7-8-7.
https://doi.org/10.26421/QIC14.7-8-7
[52] S. Virmani, S. F. Huelga, and M. B. Plenio, Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71, 042328 (2005). DOI: 10.1103/PhysRevA.71.042328.
https://doi.org/10.1103/PhysRevA.71.042328
[53] Napp, J., La Placa, R., Dalzell, A., Brandao, F. & Harrow, A. Efficient classical simulation of random shallow 2D quantum circuits. ArXiv Preprint ArXiv:2001.00021. (2019). DOI: 10.48550/arXiv.2001.00021.
https://doi.org/10.48550/arXiv.2001.00021
[54] Noh, K., Jiang, L. & Fefferman, B. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum. 4 pp. 318 (2020). DOI: 10.22331/q-2020-09-11-318.
https://doi.org/10.22331/q-2020-09-11-318
[55] Okay, C., Zurel, M. & Raussendorf, R. On the extremal points of the $Lambda$ -polytopes and classical simulation of quantum computation with magic states. Quantum Info. and Comput. 21 No.13 & 14, 1533-7146 (2021). DOI: 10.26421/QIC21.13-14-2.
https://doi.org/10.26421/QIC21.13-14-2
[56] Pashayan, H., Reardon-Smith, O., Korzekwa, K. & Bartlett, S. Fast estimation of outcome probabilities for quantum circuits. Quantum 5, 606 (2021). DOI: 10.1103/PRXQuantum.3.020361.
https://doi.org/10.1103/PRXQuantum.3.020361
[57] Gosset, D., Grier, D., Kerzner, A. & Schaeffer, L. Fast simulation of planar Clifford circuits. ArXiv Preprint ArXiv:2009.03218. (2020). DOI: 10.48550/arXiv.2009.03218.
https://doi.org/10.48550/arXiv.2009.03218
[58] Van den Nest, M. Universal quantum computation with little entanglement. Physical Review Letters. 110, 060504 (2013). DOI: 10.1103/PhysRevLett.110.060504.
https://doi.org/10.1103/PhysRevLett.110.060504
[59] Qassim, H., Pashayan, H. & Gosset, D. Improved upper bounds on the stabilizer rank of magic states. ArXiv Preprint ArXiv:2106.07740. (2021). DOI: 10.48550/arXiv.2106.07740.
https://doi.org/10.48550/arXiv.2106.07740
[60] Raussendorf, R., Bermejo-Vega, J., Tyhurst, E., Okay, C. & Zurel, M. Phase-space-simulation method for quantum computation with magic states on qubits. Physical Review A. 101, 012350 (2020). DOI: 10.1103/PhysRevA.101.012350.
https://doi.org/10.1103/PhysRevA.101.012350
[61] Schwarz, M. & Van den Nest, M. Simulating quantum circuits with sparse output distributions. ArXiv Preprint ArXiv:1310.6749. (2013). DOI: 10.48550/arXiv.1310.6749.
https://doi.org/10.48550/arXiv.1310.6749
[62] Seddon, J., Regula, B., Pashayan, H., Ouyang, Y. & Campbell, E. Quantifying quantum speedups: Improved classical simulation from tighter magic monotones. PRX Quantum. 2, 010345 (2021).DOI: 10.1103/PRXQuantum.2.010345.
https://doi.org/10.1103/PRXQuantum.2.010345
[63] H. Pashayan, J. J. Wallman, and S. D. Bartlett, Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities. Phys. Rev. Lett. 115, 070501 (2015). DOI: 10.1103/PhysRevLett.115.070501.
https://doi.org/10.1103/PhysRevLett.115.070501
[64] Van den Nest, M. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comp. 10, 3-4 pp. pp0258-0271 (2010). DOI: 10.26421/QIC10.3-4-6.
https://doi.org/10.26421/QIC10.3-4-6
[65] Van den Nest, M., Dür, W., Vidal, G. & Briegel, H. Classical simulation versus universality in measurement-based quantum computation. Physical Review A. 75, 012337 (2007). DOI: 10.1103/PhysRevA.75.012337.
https://doi.org/10.1103/PhysRevA.75.012337
Zurel, M., Okay, C. & Raussendorf, R. Hidden Variable Model for Universal Quantum Computation with Magic States on Qubits. Physical Review Letters. 125, 260404 (2020).DOI: 10.1103/PhysRevLett.125.260404.
https://doi.org/10.1103/PhysRevLett.125.260404
[67] Gross, D., Eisert, J., Schuch, N. & Perez-Garcia, D. Measurement-based quantum computation beyond the one-way model. Physical Review A. 76, 052315 (2007). DOI: 10.1103/PhysRevA.76.052315.
https://doi.org/10.1103/PhysRevA.76.052315
[68] M. Van den Nest, A. Miyake, W. Dür, H. J. Briegel, Universal Resources for Measurement-Based Quantum Computation. Phys. Rev. Lett. 97, 150504 (2006).DOI: 10.1103/PhysRevLett.97.150504.
https://doi.org/10.1103/PhysRevLett.97.150504
[69] Jozsa, R. On the simulation of quantum circuits. ArXiv Preprint Quant-ph/0603163. (2006). DOI: 10.48550/arXiv.quant-ph/0603163.
https://doi.org/10.48550/arXiv.quant-ph/0603163
arXiv:quant-ph/0603163
[70] F. Verstraete, M. Popp, and J. I. Cirac, Entanglement versus Correlations in Spin Systems. Phys. Rev. Lett. 92, 027901 (2004). DOI: 10.1103/PhysRevLett.92.027901.
https://doi.org/10.1103/PhysRevLett.92.027901
[71] A. Kissinger, J. van de Wetering, Universal MBQC with generalised parity-phase interactions and Pauli measurements. Quantum 3, 134 (2019). DOI: 10.22331/q-2019-04-26-134.
https://doi.org/10.22331/q-2019-04-26-134
[72] Y. Takeuchi, T. Morimae, M. Hayashi, Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements. Sci Rep. 9, 13585 (2019). DOI: 10.1038/s41598-019-49968-3.
https://doi.org/10.1038/s41598-019-49968-3
[73] J. Miller, A. Miyake. Hierarchy of universal entanglement in 2D measurement-based quantum computation. npj Quantum Information 2, 16036 (2016). DOI: 10.1038/npjqi.2016.36.
https://doi.org/10.1038/npjqi.2016.36
[74] M. Gachechiladze, O. Gühne, A. Miyake. Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states. Phys. Rev. A, 99, 052304 (2019). DOI: 10.1103/PhysRevA.99.052304.
https://doi.org/10.1103/PhysRevA.99.052304
[75] D. L. Zhou, B. Zeng, Z. Xu, and C. P. Sun, Quantum computation based on d-level cluster state. Phys. Rev. A 68, 062303 (2003); W. Hall, Cluster state quantum computation for many-level systems. Quant. Inf. & Comp., 7, Issue 3 pp 184–208 (2007). DOI: 10.1103/PhysRevA.68.0623034.
https://doi.org/10.1103/PhysRevA.68.0623034
[76] L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix. Phys. Lett. A 183, 1, P.14-18 (1993). DOI: 10.1016/0375-9601(93)90880-9.
https://doi.org/10.1016/0375-9601(93)90880-9
[77] H. Pashayan, S Bartlett, and D. Gross, From estimation of quantum probabilities to simulation of quantum circuits. Quantum 4, 223 (2020). DOI: 10.22331/q-2020-01-13-223.
https://doi.org/10.22331/q-2020-01-13-223
[78] L. Gurvitz and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state. Phys. Rev. A, 66, 062311 (2002) DOI: 10.1103/PhysRevA.66.062311.
https://doi.org/10.1103/PhysRevA.66.062311
[79] B. Terhal, Bell inequalities and the separability criterion. Phys. Lett. A, 271, 319 (2000). DOI: 10.1016/S0375-9601(00)00401-1.
https://doi.org/10.1016/S0375-9601(00)00401-1
[80] M. Van den Nest, Simulating quantum computers with probabilistic methods. Quant. Inf. Comp. 11, 9-10 pp. 784-812 (2011) DOI: 10.26421/QIC11.9-10-5.
https://doi.org/10.26421/QIC11.9-10-5
[81] H. J. Garcia, I. L. Markov, and A. W. Cross. Efficient inner-product algorithm for stabilizer states. arXiv preprint arXiv:1210.6646, (2012). DOI: 10.48550/arXiv.1210.6646.
https://doi.org/10.48550/arXiv.1210.6646
arXiv:1210.6646
[82] S. Bravyi, G. Smith, and J. A. Smolin. Trading classical and quantum computational resources. Physical Review X, 6:021043, (2016). DOI: 10.1103/PhysRevX.6.021043.
https://doi.org/10.1103/PhysRevX.6.021043
[83] H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger, New limits on fault-tolerant quantum computation. Proc. of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (IEEE, New York, 2006), pp. 411–419. DOI: 10.1109/FOCS.2006.50.
https://doi.org/10.1109/FOCS.2006.50
[84] L. G. Valiant, Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229–1254, (2002). DOI: 10.1137/S0097539700377025.
https://doi.org/10.1137/S0097539700377025
[85] B. M. Terhal and D. P. DiVincenzo, Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A, 65(3):032325, (2002). DOI: 10.1103/PhysRevA.65.032325.
https://doi.org/10.1103/PhysRevA.65.032325
[86] M. B. Hastings, An area law for one dimensional quantum systems. J. Stat. Mech., 2007:08024, (2007). DOI: 10.1088/1742-5468/2007/08/P08024.
https://doi.org/10.1088/1742-5468/2007/08/P08024
[87] E. F. Galvao, Discrete Wigner functions and quantum computational speedup. Phys. Rev. A 71, 042302 (2005). DOI: 10.1103/PhysRevA.71.042302 ; C. Cormick, E. F. Galvao, D. Gottesman, J. P. Paz, and A. O. Pittenger, Classicality in discrete Wigner functions, Phys. Rev. A 73 012301 (2006). DOI: 10.1103/PhysRevA.71.042302.
https://doi.org/10.1103/PhysRevA.71.042302
[88] D. J. Brod, Efficient classical simulation of matchgate circuits with generalized inputs and measurements. Phys. Rev. A 93, 062332 (2016) DOI: 10.1103/PhysRevA.93.062332.
https://doi.org/10.1103/PhysRevA.93.062332
[89] Arute et. al., Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. DOI: 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[90] R. Raz, Exponential separation of quantum and classical communication complexity. Proc. 31st Annual ACM Symp. Theory of Computing, pages 358–367, (1999). DOI: 10.1145/301250.301343.
https://doi.org/10.1145/301250.301343
[91] F Pan, K Chen and P Zhan, Solving the sampling problem of the sycamore quantum circuits. Phys. Rev. Lett. 129 (9), 090502 (2022). DOI: 10.1103/PhysRevLett.129.090502.
https://doi.org/10.1103/PhysRevLett.129.090502
[92] D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. arXiv:2211.03999, (2022). DOI: 10.48550/arXiv.2211.03999.
https://doi.org/10.48550/arXiv.2211.03999
arXiv:2211.03999
[93] S. Popescu and D. Rohrlich, Generic quantum nonlocality. Phys. Lett. A 166, 293 (1992). DOI: 10.1016/0375-9601(92)90711-T.
https://doi.org/10.1016/0375-9601(92)90711-T
[94] R. Somma, H. Barnum, G. Ortiz, and E. Knill, Efficient Solvability of Hamiltonians and Limits on the Power of Some Quantum Computational Models. Phys. Rev. Lett. 97, 190501 (2006). DOI: 10.1103/PhysRevLett.97.190501.
https://doi.org/10.1103/PhysRevLett.97.190501
Cited by
[1] Sahar Atallah, Michael Garn, Yukuan Tao, and Shashank Virmani, “Classically efficient regimes in measurement based quantum computation performed using diagonal two qubit gates and cluster measurements”, arXiv:2307.01800, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2024-02-07 02:00:24). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2024-02-07 02:00:22).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2024-02-06-1243/
