Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1108.4909 · Physical Review A

Strategies for measurement-based quantum computation with cluster states transformed by stochastic local operations and classical communication

Adam G. D’Souza, David L. Feder

Published Oct 3, 2011• 3 citations
arXivHTMLPDF

Abstract

We examine cluster states transformed by stochastic local operations and classical communication, as a resource for deterministic universal computation driven strictly by projective measurements. We identify circumstances under which such states in one dimension constitute resources for random-length single-qubit rotations, in one case quasideterministically ($N\ensuremath{-}U\ensuremath{-}N$ states) and in another probabilistically ($B\ensuremath{-}U\ensuremath{-}B$ states). In contrast to the cluster states, the $N\ensuremath{-}U\ensuremath{-}N$ states exhibit spin correlation functions that decay exponentially with distance, while the $B\ensuremath{-}U\ensuremath{-}B$ states can be arbitrarily locally pure. A two-dimensional square $N\ensuremath{-}U\ensuremath{-}N$ lattice is a universal resource for quasideterministic measurement-based quantum computation. Measurements on cubic $B\ensuremath{-}U\ensuremath{-}B$ states yield two-dimensional cluster states with bond defects, whose connectivity exceeds the percolation threshold for a critical value of the local purity.

DOI
10.1103/physreva.84.042301

Related papers

Measurement-based quantum computation beyond the one-way model

D. Gross, Jens Eisert, Norbert Schuch +1 more

We introduce schemes for quantum computing based on local measurements on entangled resource states. This work elaborates on the framework established in Gross and Eisert [Phys. Rev. Lett. 98, 220503 (2007); quant-ph/0609149]. Our method makes use of tools from many-body physics---matrix product states, finitely correlated states, or projected entangled pairs states---to show how measurements on entangled states can be viewed as processing quantum information. This work hence constitutes an instance where a quantum information problem---how to realize quantum computation---was approached using tools from many-body theory and not vice versa. We give a more detailed description of the setting and present a large number of examples. We find computational schemes, which differ from the original one-way computer, for example, in the way the randomness of measurement outcomes is handled. Also, schemes are presented where the logical qubits are no longer strictly localized on the resource state. Notably, we find a great flexibility in the properties of the universal resource states: They may, for example, exhibit nonvanishing long-range correlation functions or be locally arbitrarily close to a pure state. We discuss variants of Kitaev's toric code states as universal resources, and contrast this with situations where they can be efficiently classically simulated. This framework opens up a way of thinking of tailoring resource states to specific physical systems, such as cold atoms in optical lattices or linear optical systems.

arXiv:0706.3401•Physical Review A•Nov 19, 2007•236 citations

Universal resources for approximate and stochastic measurement-based quantum computation

Caterina E. Mora, Marco Piani, Akimasa Miyake +3 more

We investigate which quantum states can serve as universal resources for approximate and stochastic measurement-based quantum computation in the sense that any quantum state can be generated from a given resource by means of single-qubit (local) operations assisted by classical communication. More precisely, we consider the approximate and stochastic generation of states, resulting, for example, from a restriction to finite measurement settings or from possible imperfections in the resources or local operations. We show that entanglement-based criteria for universality obtained in M. Van den Nest et al. [New J. Phys. 9, 204 (2007)] for the exact, deterministic case can be lifted to the much more general approximate, stochastic case. This allows us to move from the idealized situation (exact, deterministic universality) considered in previous works to the practically relevant context of nonperfect state preparation. We find that any entanglement measure fulfilling some basic requirements needs to reach its maximum value on some element of an approximate, stochastic universal family of resource states, as the resource size grows. This allows us to rule out various families of states as being approximate, stochastic universal. We prove that approximate, stochastic universality is in general a weaker requirement than deterministic, exact universality and provide resources that are efficient approximate universal, but not exact deterministic universal. We also study the robustness of universal resources for measurement-based quantum computation under realistic assumptions about the (imperfect) generation and manipulation of entangled states, giving an explicit expression for the impact that errors made in the preparation of the resource have on the possibility to use it for universal approximate and stochastic state preparation. Finally, we discuss the relation between our entanglement-based criteria and recent results regarding the uselessness of states with a high degree of geometric entanglement as universal resources [D. Gross et al., Phys. Rev. Lett. 102, 190501 (2009); M. J. Bremner et al., Phys. Rev. Lett 102, 190502 (2009)].

arXiv:0904.3641•Physical Review A•Apr 22, 2010•25 citations

Novel Schemes for Measurement-Based Quantum Computation

D. Gross, Jens Eisert

We establish a framework which allows one to construct novel schemes for measurement-based quantum computation. The technique develops tools from many-body physics-based on finitely correlated or projected entangled pair states-to go beyond the cluster-state based one-way computer. We identify resource states radically different from the cluster state, in that they exhibit nonvanishing correlations, can be prepared using nonmaximally entangling gates, or have very different local entanglement properties. In the computational models, randomness is compensated in a different manner. It is shown that there exist resource states which are locally arbitrarily close to a pure state. We comment on the possibility of tailoring computational models to specific physical systems.

arXiv:quant-ph/0609149•Physical Review Letters•May 31, 2007•253 citations

Resource states and temporal order of the measurement-based model of quantum computation

Poya Haghnegahdar

Measurement-based quantum computation (MBQC) performs quantum algorithms by local, adaptive measurements on an initially entangled many-body "resource" state. This thesis investigates MBQC through two tightly coupled lenses: (i) which physical states and phases of matter constitute universal resources, and (ii) how the temporal order induced by measurement adaptivity constrains and, in turn, is constrained by those resources. Resources from valence-bond constructions. We develop hybrid AKLT-type (valence-bond) resources on two-dimensional lattices and show how a generalized POVM reduces higher-spin degrees of freedom to effective qubits while preserving computational viability. We analyze worst-case and frustrated geometries (e.g., kagome and decorated lattices), identify planarity-restoring local operations, and use percolation-style diagnostics on the induced graph states to certify universality beyond idealized cluster-state settings. A two-parameter phase with noisy POVMs. Extending ground states across a phase connected to the AKLT point, we introduce a measurement-noise–aware framework with probabilistic restoration and closed-form weight formulae derived via a graphical (g-)calculus. Large-scale numerics that account for correlations map a two-parameter phase diagram and delineate regimes of universal vs. non-universal post-measurement graphs. These results exhibit a robust universal region that persists away from ideal measurements and clarify how noise and Hamiltonian deformation jointly control computational power. Temporal order and determinism. We develop a stabilizer-and-influence-matrix formalism that places temporal dependencies on the same footing as resource structure. Four theorems establish a two-way determination between (a) the classical processing relations (including the influence matrix that generates the partial order of measurements) and (b) the resource stabilizer in a normal form, up to local equivalence. This links gauge freedoms, byproduct handling, and flow/gflow–style constraints into a unified picture of when adaptive measurement schedules yield deterministic computation. Together, these contributions clarify when physically motivated ground states serve as universal MBQC resources under realistic measurement noise, and how temporal constraints fundamentally shape the space of admissible computations in MBQC.

•Jan 1, 2026•0 citations

One Polynomial Strategy for Computing Local Projections on Square-Lattice Cluster States

Nyau Fisn, Hung‐Lin Fu

Quantum computing has attracted a lot of attention in recent years. It is one of the promising candidates for the next-generation computing paradigms. Basically, there are two technical lines to realize quantum computing. One is composing the unitary operators of a few qubits to achieve general unitary operators on an arbitrary number of qubits, known as the approach of quantum circuits. The other one focuses on preparing quantum cluster states and performing the computation by measuring the states with a particular basis, known as measurement-based quantum computing or one-way quantum computing. The two strategies have been proven to be equivalent to each other. This note aims to discuss the strategies for computing the local projections on square-lattice cluster states. Seemingly, one strategy for the computation could require both polynomial steps and memories. In particular, if the number of qubits in a square-lattice is denoted by $N$, the step number for computing an arbitrary local projection on the state could be proportional to a polynomial of $N$ under a bounded cost of memory. Consider that the square-lattice cluster states are one kind of universal computing resource, the results might be helpful for understanding the computational advantages of quantum algorithms, as well as the limits of the numerical analysis on other relevant quantum models. Although the results in the note are not peer reviewed, we would like to make them public because they are quite easy to check.

arXiv:2506.14257•Jun 17, 2025•0 citations

Quantum computational universality of the Cai-Miyake-Dür-Briegel two-dimensional quantum state from Affleck-Kennedy-Lieb-Tasaki quasichains

Tzu-Chieh Wei, Robert Raussendorf, L. C. Kwek

Universal quantum computation can be achieved by simply performing single-qubit measurements on a highly entangled resource state, such as cluster states. Cai, Miyake, D\"ur, and Briegel recently constructed a ground state of a two-dimensional quantum magnet by combining multiple Affleck-Kennedy-Lieb-Tasaki quasichains of mixed spin-3/2 and spin-1/2 entities and by mapping pairs of neighboring spin-1/2 particles to individual spin-3/2 particles [Phys. Rev. A 82, 052309 (2010)]. They showed that this state enables universal quantum computation by single-spin measurements. Here, we give an alternative understanding of how this state gives rise to universal measurement-based quantum computation: by local operations, each quasichain can be converted to a one-dimensional cluster state and entangling gates between two neighboring logical qubits can be implemented by single-spin measurements. We further argue that a two-dimensional cluster state can be distilled from the Cai-Miyake-D\"ur-Briegel state.

arXiv:1105.5635•Physical Review A•Oct 19, 2011•8 citations
We examine cluster states transformed by stochastic local operations and classical communication, as a resource for deterministic universal computation driven strictly by projective measurements. We identify circumstances under which such states in one dimension constitute resources for random-length single-qubit rotations, in one case quasideterministically (N\ensuremath−U\ensuremath−NN\ensuremath{-}U\ensuremath{-}NN\ensuremath−U\ensuremath−N states) and in another probabilistically (B\ensuremath−U\ensuremath−BB\ensuremath{-}U\ensuremath{-}BB\ensuremath−U\ensuremath−B states). In contrast to the cluster states, the N\ensuremath−U\ensuremath−NN\ensuremath{-}U\ensuremath{-}NN\ensuremath−U\ensuremath−N states exhibit spin correlation functions that decay exponentially with distance, while the B\ensuremath−U\ensuremath−BB\ensuremath{-}U\ensuremath{-}BB\ensuremath−U\ensuremath−B states can be arbitrarily locally pure. A two-dimensional square N\ensuremath−U\ensuremath−NN\ensuremath{-}U\ensuremath{-}NN\ensuremath−U\ensuremath−N lattice is a universal resource for quasideterministic measurement-based quantum computation. Measurements on cubic B\ensuremath−U\ensuremath−BB\ensuremath{-}U\ensuremath{-}BB\ensuremath−U\ensuremath−B states yield two-dimensional cluster states with bond defects, whose connectivity exceeds the percolation threshold for a critical value of the local purity.
We introduce schemes for quantum computing based on local measurements on entangled resource states. This work elaborates on the framework established in Gross and Eisert [Phys. Rev. Lett. 98, 220503 (2007); quant-ph/0609149]. Our method makes use of tools from many-body physics---matrix product states, finitely correlated states, or projected entangled pairs states---to show how measurements on entangled states can be viewed as processing quantum information. This work hence constitutes an instance where a quantum information problem---how to realize quantum computation---was approached using tools from many-body theory and not vice versa. We give a more detailed description of the setting and present a large number of examples. We find computational schemes, which differ from the original one-way computer, for example, in the way the randomness of measurement outcomes is handled. Also, schemes are presented where the logical qubits are no longer strictly localized on the resource state. Notably, we find a great flexibility in the properties of the universal resource states: They may, for example, exhibit nonvanishing long-range correlation functions or be locally arbitrarily close to a pure state. We discuss variants of Kitaev's toric code states as universal resources, and contrast this with situations where they can be efficiently classically simulated. This framework opens up a way of thinking of tailoring resource states to specific physical systems, such as cold atoms in optical lattices or linear optical systems.
We investigate which quantum states can serve as universal resources for approximate and stochastic measurement-based quantum computation in the sense that any quantum state can be generated from a given resource by means of single-qubit (local) operations assisted by classical communication. More precisely, we consider the approximate and stochastic generation of states, resulting, for example, from a restriction to finite measurement settings or from possible imperfections in the resources or local operations. We show that entanglement-based criteria for universality obtained in M. Van den Nest et al. [New J. Phys. 9, 204 (2007)] for the exact, deterministic case can be lifted to the much more general approximate, stochastic case. This allows us to move from the idealized situation (exact, deterministic universality) considered in previous works to the practically relevant context of nonperfect state preparation. We find that any entanglement measure fulfilling some basic requirements needs to reach its maximum value on some element of an approximate, stochastic universal family of resource states, as the resource size grows. This allows us to rule out various families of states as being approximate, stochastic universal. We prove that approximate, stochastic universality is in general a weaker requirement than deterministic, exact universality and provide resources that are efficient approximate universal, but not exact deterministic universal. We also study the robustness of universal resources for measurement-based quantum computation under realistic assumptions about the (imperfect) generation and manipulation of entangled states, giving an explicit expression for the impact that errors made in the preparation of the resource have on the possibility to use it for universal approximate and stochastic state preparation. Finally, we discuss the relation between our entanglement-based criteria and recent results regarding the uselessness of states with a high degree of geometric entanglement as universal resources [D. Gross et al., Phys. Rev. Lett. 102, 190501 (2009); M. J. Bremner et al., Phys. Rev. Lett 102, 190502 (2009)].
We establish a framework which allows one to construct novel schemes for measurement-based quantum computation. The technique develops tools from many-body physics-based on finitely correlated or projected entangled pair states-to go beyond the cluster-state based one-way computer. We identify resource states radically different from the cluster state, in that they exhibit nonvanishing correlations, can be prepared using nonmaximally entangling gates, or have very different local entanglement properties. In the computational models, randomness is compensated in a different manner. It is shown that there exist resource states which are locally arbitrarily close to a pure state. We comment on the possibility of tailoring computational models to specific physical systems.
Measurement-based quantum computation (MBQC) performs quantum algorithms by local, adaptive measurements on an initially entangled many-body "resource" state. This thesis investigates MBQC through two tightly coupled lenses: (i) which physical states and phases of matter constitute universal resources, and (ii) how the temporal order induced by measurement adaptivity constrains and, in turn, is constrained by those resources. Resources from valence-bond constructions. We develop hybrid AKLT-type (valence-bond) resources on two-dimensional lattices and show how a generalized POVM reduces higher-spin degrees of freedom to effective qubits while preserving computational viability. We analyze worst-case and frustrated geometries (e.g., kagome and decorated lattices), identify planarity-restoring local operations, and use percolation-style diagnostics on the induced graph states to certify universality beyond idealized cluster-state settings. A two-parameter phase with noisy POVMs. Extending ground states across a phase connected to the AKLT point, we introduce a measurement-noise–aware framework with probabilistic restoration and closed-form weight formulae derived via a graphical (g-)calculus. Large-scale numerics that account for correlations map a two-parameter phase diagram and delineate regimes of universal vs. non-universal post-measurement graphs. These results exhibit a robust universal region that persists away from ideal measurements and clarify how noise and Hamiltonian deformation jointly control computational power. Temporal order and determinism. We develop a stabilizer-and-influence-matrix formalism that places temporal dependencies on the same footing as resource structure. Four theorems establish a two-way determination between (a) the classical processing relations (including the influence matrix that generates the partial order of measurements) and (b) the resource stabilizer in a normal form, up to local equivalence. This links gauge freedoms, byproduct handling, and flow/gflow–style constraints into a unified picture of when adaptive measurement schedules yield deterministic computation. Together, these contributions clarify when physically motivated ground states serve as universal MBQC resources under realistic measurement noise, and how temporal constraints fundamentally shape the space of admissible computations in MBQC.
Quantum computing has attracted a lot of attention in recent years. It is one of the promising candidates for the next-generation computing paradigms. Basically, there are two technical lines to realize quantum computing. One is composing the unitary operators of a few qubits to achieve general unitary operators on an arbitrary number of qubits, known as the approach of quantum circuits. The other one focuses on preparing quantum cluster states and performing the computation by measuring the states with a particular basis, known as measurement-based quantum computing or one-way quantum computing. The two strategies have been proven to be equivalent to each other. This note aims to discuss the strategies for computing the local projections on square-lattice cluster states. Seemingly, one strategy for the computation could require both polynomial steps and memories. In particular, if the number of qubits in a square-lattice is denoted by NNN, the step number for computing an arbitrary local projection on the state could be proportional to a polynomial of NNN under a bounded cost of memory. Consider that the square-lattice cluster states are one kind of universal computing resource, the results might be helpful for understanding the computational advantages of quantum algorithms, as well as the limits of the numerical analysis on other relevant quantum models. Although the results in the note are not peer reviewed, we would like to make them public because they are quite easy to check.
Universal quantum computation can be achieved by simply performing single-qubit measurements on a highly entangled resource state, such as cluster states. Cai, Miyake, D\"ur, and Briegel recently constructed a ground state of a two-dimensional quantum magnet by combining multiple Affleck-Kennedy-Lieb-Tasaki quasichains of mixed spin-3/2 and spin-1/2 entities and by mapping pairs of neighboring spin-1/2 particles to individual spin-3/2 particles [Phys. Rev. A 82, 052309 (2010)]. They showed that this state enables universal quantum computation by single-spin measurements. Here, we give an alternative understanding of how this state gives rise to universal measurement-based quantum computation: by local operations, each quasichain can be converted to a one-dimensional cluster state and entangling gates between two neighboring logical qubits can be implemented by single-spin measurements. We further argue that a two-dimensional cluster state can be distilled from the Cai-Miyake-D\"ur-Briegel state.