CoChat
Sign Up
Cited by 1,655Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index; none of the 30 sources its claims cite is checked for support yet.

Measurement-based quantum computation on cluster states

Open access
Raussendorf, Robert, Browne, Daniel E., Briegel, Hans J.·2003·Physical Review A
DOI 10.1103/physreva.68.022312
Open this paper in CoChat — free accountOpen PDF

Abstract

We give a detailed account of the one-way quantum computer, a scheme of quantum computation that consists entirely of one-qubit measurements on a particular class of entangled states, the cluster states. We prove its universality, describe why its underlying computational model is different from the network model of quantum computation, and relate quantum algorithms to mathematical graphs. Further we investigate the scaling of required resources and give a number of examples for circuits of practical interest such as the circuit for quantum Fourier transformation and for the quantum adder. Finally, we describe computation with clusters of finite size.

Overview

AI snapshot

Written from the paper’s full text.

TL;DR

The paper gives a detailed account of the one-way quantum computer (QC_C), in which computation is performed solely by one-qubit measurements on a cluster state, and proves its universality by efficient simulation of quantum logic networks. It also relates algorithms to graphs, analyzes resource scaling, and provides example circuits including quantum Fourier transformation and an n-qubit adder.

Key findings

  • The QC_C is universal: any unitary quantum logic network can be simulated efficiently. A CNOT gate is realized on a cluster of 15 qubits, and an arbitrary one-qubit rotation on a chain of 5 qubits; all Clifford-group circuits have unit logical depth and can be realized in a single time step.
  • Resource bounds relative to the network model are polynomial: \(T \le 3T_{\text{qln}}\), \(S \le 24 S_{\text{qln}}^2 T_{\text{qln}}\), and \(S \le 24 O_{\text{qln}} S_{\text{qln}}\), \(O \le 24 O_{\text{qln}} S_{\text{qln}}\). For quantum Fourier transformation, \(T=n\), \(S,O=2n^2\), versus network \(T_{\text{qln}}=2n\), \(S_{\text{qln}}=n\), \(O_{\text{qln}}=n^2/2\). For the n-qubit adder, \(S=O=304n\), \(T=n\), versus network \(S_{\text{qln}}=3n\), \(O_{\text{qln}}=T_{\text{qln}}=8n\); the QC_C uses about 100 times more spatial and 38 times more operational resources while being 8 times faster.
  • The Clifford part of any quantum algorithm can be removed; the remaining algorithm-specific non-universal quantum resource is a graph state, and only non-Clifford gates require quantum resources.
  • Computation on finite clusters is possible by repeated re-entangling and measurement rounds, which can split long computations and bound the decoherence exposure time of each cluster qubit.

Methods

  • Theoretical and constructive analysis: cluster states are defined by eigenvalue equations and related to graph states; they can be created via an Ising-type interaction.
  • Universality is proved by showing that gate simulations can be concatenated, using Scheme 1/Scheme 2 and Theorem 1, a criterion based on \(2n\) eigenvalue equations, byproduct operators, and adaptive measurement bases.
  • The paper analyzes resource scaling and gives explicit measurement patterns for gates and subcircuits, including CNOT, arbitrary rotations, controlled phase, Toffoli, CARRY, swap, Hamiltonian simulation, quantum Fourier transformation, and addition.

Limitations

  • The paper states that the resource upper bounds “should not be taken for estimates,” that a spatial overhead always exists, and that in the finite-cluster variant the Clifford part may no longer be performed in a single time step. It also states that a proposed new composition principle based on generalized rotations is “Not yet” clear.
  • Evident from the text: the work is theoretical and does not report an experimental implementation or a fault-tolerance threshold analysis; decoherence is discussed qualitatively as a motivation for splitting computations, not quantified.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1103/physreva.68.022312

Cites

48 of 48 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 of 30 cited sources checked · 0 supported · 0 flagged

Show all 208 claims

  • Probably not a substantial claim. 46
  • It may state two separate claims as one. 56
  • The quote only partly states this claim. 2
99 of 99

  • The authors state this as an assumption.

    The readout measurements are performed in the σ_z eigenbasis.

    “Without loss of generality, we assume in this paper that the readout measurements are performed in the σ z -eigenbasis.”

  • The authors state this as an assumption.

    For the sub-cluster C_N, κ'_a = 0 for all a ∈ C_N.

    “We assume that κ ′ a = 0 for all a ∈ C N .”

  • The paper relies on this without support.

    Individual measurement outcomes in the QC_C scheme are random and uncontrollable.

    “Thus one can perform measurements specified by a spatial and temporal pattern of measurement bases but one cannot control into which of the two eigenstates the qubits are projected.”

  • The authors state this as an assumption.

    In the network model, a general rotation can be realized in a single step.

    “Rather we assume that in the network model a rotation can be realized in a single step.”

  • The authors state this as an assumption.

    For counting the operational and temporal network resources, the three-qubit controlled spinflip gate used in the addition circuit is composed of two Toffoli gates and one CNOT-gate, and the CNOT and Toffoli gates are regarded as elementary.

    “For the counting of the operational and temporal network resources we have assumed that the three-qubit controlled spinflip gate used in the addition circuit is composed of two Toffoli gates and one CNOT-gate as described in [23], and that the CNOT-and the Toffoli-gate are regarded as elementary.”

  • The paper relies on this without support.

    Any unitary transformation may be decomposed into a unitary transformation in the Clifford group followed by generalized rotations.

    “Any unitary transformation may be decomposed into a unitary transformation in the Clifford group followed by generalized rotations.”
6 of 6

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?

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 1

  1. R. Raussendorf, 2002, Quantum Inf. Comput., 6, 443

Cited by

Sorted by citations

See all 1,655

Related

See all

Metadata

Authors
Raussendorf, R., Browne, D. E., & Briegel, H. J.
Affiliations
Ludwig-Maximilians-Universität München (DE)
ORCID
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2003-08-25
Volume
68
Issue
2
ISSN
  • 0556-2791 (ISSN-L)
  • 1050-2947
  • 1094-1622
DOI
10.1103/physreva.68.022312
OpenAlex
W2103368228
Semantic Scholar
adb89e8fcb7226a67a97929bfe85843c9243acaf
Cited by
1,655
References
45
Citations by year
2026: 71 · 2025: 121 · 2024: 132 · 2023: 106 · 2022: 83 · 2021: 84 · 2020: 82 · 2019: 72 · 2018: 65 · 2017: 73 · 2016: 63 · 2015: 42 · 2014: 69 · 2013: 59 · 2012: 71
FWCI
45.44
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
  • Elektronische Hochschulschriften der LMU München (Ludwig-Maximilians-Universität München) (submittedVersion)
  • UCL Discovery (University College London) (submittedVersion)
  • arXiv (Cornell University)
Funders
Deutsche Forschungsgemeinschaft
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
measurement-based quantum computation, cluster states, universality, entangled states, quantum networks, quantum algorithms, graph theory, resource scaling, quantum Fourier transform, quantum adder, finite clusters

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.

A language model drew the claims from the paper on 2026-10-09, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-09 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

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