Classical Simulation of Limited-Width Cluster-State Quantum Computation
Open accessAbstract
We present a classical protocol, using the matrix product-state representation, to simulate cluster-state quantum computation at a cost polynomial in the number of qubits in the cluster and exponential in d---the width of the cluster. We use this result to show that any log-depth quantum computation in the gate array model, with gates linking only nearby qubits, can be simulated efficiently on a classical computer.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For the majority of states identified as not universal, efficient classical simulation is possible; specifically, the outcome probabilities of any sequence of single-qubit measurements can be efficiently and exactly computed.
“For example, for the majority of states which have been identified above as not being universal, one has shown that efficient classical simulation is possible. More precisely, for such states it is possible to efficiently and exactly compute the outcome probabilities of any sequence of single-qubit measurements.”
From Measurement-based quantum computation (2009) · cites this paper as [90]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477 · see citing works
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368 · see citing works
Vidal, G. (2000) · Journal of Modern Optics · doi:10.1080/095003400148268 · Cited by 134 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Classical simulation versus universality in measurement-based quantum computation
Van den Nest, M., Dür, W., Vidal, G., & Briegel, H. J. (2007) · Physical Review A · doi:10.1103/physreva.75.012337 · Cited by 95 · see citing works
Fundamentals of universality in one-way quantum computation
Nest, M. V. D., Dür, W., Miyake, A., & Briegel, H. J. (2007) · New Journal of Physics · doi:10.1088/1367-2630/9/6/204 · Cited by 97 · see citing works
Measurement-Based Quantum Computation and Undecidable Logic
Van den Nest, M., & Briegel, H. J. (2008) · Foundations of Physics · doi:10.1007/s10701-008-9212-6 · Cited by 17 · see citing works
- Authors
- Yoran, N., & Short, A. J.
- Affiliations
- University of Bristol (GB)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2006-05-01
- Volume
- 96
- Issue
- 17
- Pages
- 170503-170503
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1974957435
- Cited by
- 33
- References
- 3
- Citations by year
- 2025: 2 · 2024: 1 · 2023: 1 · 2021: 3 · 2020: 2 · 2019: 1 · 2018: 3 · 2017: 1 · 2016: 1 · 2015: 1 · 2013: 2
- FWCI
- 4.57
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- Explore Bristol Research (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Bristol Research (University of Bristol) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- classical simulation of quantum computation, cluster states, matrix product states, quantum advantage, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
