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:1705.01535 · Physical Review A

Minimal qubit resources for the realization of measurement-based quantum computation

Monireh Houshmand, Mahboobeh Houshmand, Joseph F. Fitzsimons

Published Jul 17, 2018• 11 citations
arXivHTMLPDF

Abstract

In measurement-based quantum computation (MBQC), a special highly entangled state (called a resource state) allows for universal quantum computation driven by single-qubit measurements and postmeasurement corrections. The large number of qubits necessary to construct the resource state constitutes one of the main down sides to MBQC. However, in some instances it is possible to extend the resource state on the fly, meaning that not every qubit must be realized in the devices simultaneously. We consider the question of the minimal number of physical qubits that must be present in a system to directly implement a given measurement pattern. For measurement patterns which have quantum circuit representation as formalized by the notion of flow, with $n$ inputs, $n$ outputs, and $m$ total qubits, we show that only a minimum of $n+1$ and $m$ qubits are required, while the number of required qubits can be as high as $m\ensuremath{-}2$ for measurement patterns which implement a unitary but do not have a quantum circuit representation, as formalized by the notion of generalized flow (gflow). We discuss the implications of removing the Clifford part of a measurement pattern, using well-established transformation rules for Pauli measurements, for the presence of flow versus gflow, and hence the effect on the minimum number of physical qubits required to directly realize the measurement pattern.

DOI
10.1103/physreva.98.012318

Related papers

Construction of optimal resources for concatenated quantum protocols

Alexander Pirker, Julius Wallnöfer, Hans J. Briegel +1 more

We consider the explicit construction of resource states for measurement-based quantum information processing. We concentrate on special-purpose resource states that are capable to perform a certain operation or task, where we consider unitary Clifford circuits as well as non-trace-preserving completely positive maps, more specifically probabilistic operations including Clifford operations and Pauli measurements. We concentrate on $1\ensuremath{\rightarrow}m$ and $m\ensuremath{\rightarrow}1$ operations, i.e., operations that map one input qubit to $m$ output qubits or vice versa. Examples of such operations include encoding and decoding in quantum error correction, entanglement purification, or entanglement swapping. We provide a general framework to construct optimal resource states for complex tasks that are combinations of these elementary building blocks. All resource states only contain input and output qubits, and are hence of minimal size. We obtain a stabilizer description of the resulting resource states, which we also translate into a circuit pattern to experimentally generate these states. In particular, we derive recurrence relations at the level of stabilizers as key analytical tool to generate explicit (graph) descriptions of families of resource states. This allows us to explicitly construct resource states for encoding, decoding, and syndrome readout for concatenated quantum error correction codes, code switchers, multiple rounds of entanglement purification, quantum repeaters, and combinations thereof (such as resource states for entanglement purification of encoded states).

arXiv:1612.09444•Physical Review A•Jun 26, 2017•6 citations

Hierarchies of resources for measurement-based quantum computation

Markus Frembs, Sam Roberts, Earl T. Campbell +1 more

Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.

arXiv:2203.09965•New Journal of Physics•Dec 28, 2022•11 citations

Inserting Planar-Measured Qubits into MBQC Patterns while Preserving Flow

Miriam Backens, Thomas Perez

In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via single-qubit measurements on a resource state.Flow conditions ensure that the overall computation is deterministic in a suitable sense, and are required for efficient translation into quantum circuits.Procedures that rewrite MBQC patterns -e.g. for optimisation, or adapting to hardware constraints -thus need to preserve the existence of flow.Most previous work has focused on rewrites that reduce the number of qubits in the computation, or that introduce new Pauli-measured qubits.Here, we consider the insertion of planar-measured qubits into MBQC patterns, i.e. arbitrary measurements in a plane of the Bloch sphere spanned by a pair of Pauli operators; such measurements are necessary for universal MBQC.We extend the definition of causal flow, previously restricted to XY -measurements only, to also permit Y Z-measurements and derive the conditions under which a Y Z-insertion preserves causal flow.Then we derive conditions for Y Z-insertion into patterns with gflow or Pauli flow, in which case the argument straightforwardly extends to XZ-insertions as well.We also show that the 'vertex splitting' or 'neighbour unfusion' rule previously used in the literature can be derived from Y Z-insertion and pivoting.This work contributes to understanding the broad properties of flow-preserving rewriting in MBQC and in the ZX-calculus more broadly, and it will enable more efficient optimisation, obfuscation, or routing.

arXiv:2508.14671•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•0 citations

Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements

Tommy McElvanney, Miriam Backens

In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard resource state.So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these.Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits.In this work, we show that introducing new Z-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow.Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [17].We prove that any MBQClike stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow, and that each of these rules can be reversed while also preserving the existence of Pauli flow.Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.

arXiv:2205.02009•Electronic Proceedings in Theoretical Computer Science•Nov 14, 2023•9 citations

Extended Measurement Calculus

Vincent Danos A, Elham Kashefi, Prakash Panangaden +1 more

Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.” In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems. We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.

Cambridge University Press eBooks•Nov 30, 2009•38 citations

Measurement-based quantum computing with qudit stabilizer states

Alena Romanova, Wolfgang Dür

Abstract We show how to perform measurement-based quantum computing on qudits (high-dimensional quantum systems) using alternative resource states beyond the cluster state. Estimating overheads for gate decomposition, we find that generalizing standard qubit measurement patterns to the qudit cluster state is suboptimal in most dimensions, so that alternative qudit resource states could enable enhanced computational efficiency. In these resources, the entangling interaction is a block-diagonal Clifford operation rather than the usual controlled-phase gate for cluster states. This simple change has remarkable consequences: the applied entangling operation determines an intrinsic single-qudit gate associated with the resource that drives the quantum computation when performing single-qudit measurements on the resource state. We prove a condition for the intrinsic gate allowing for the measurement-based implementation of arbitrary single-qudit unitaries. Furthermore, we demonstrate for prime-power-dimensional qudits that the complexity of the realization depends linearly both on the dimension and the Pauli order of the intrinsic gate. These insights also allow us to optimize the efficiency of the standard qudit cluster state by effectively mimicking more favorable intrinsic-gate structures, thereby reducing the required measurement depth. Finally, we discuss the required two-dimensional geometry of the resource state for universal measurement-based quantum computing. As concrete examples, we present multiple alternative resource states. In certain dimensions, we show the existence of resource states achieving optimal intrinsic gates, enabling more efficient measurement-based quantum information processing than the qudit cluster state and highlighting the potential of qudit stabilizer state resources for future quantum computing architectures.

arXiv:2506.20724•Quantum Science and Technology•Jan 21, 2026•1 citation
In measurement-based quantum computation (MBQC), a special highly entangled state (called a resource state) allows for universal quantum computation driven by single-qubit measurements and postmeasurement corrections. The large number of qubits necessary to construct the resource state constitutes one of the main down sides to MBQC. However, in some instances it is possible to extend the resource state on the fly, meaning that not every qubit must be realized in the devices simultaneously. We consider the question of the minimal number of physical qubits that must be present in a system to directly implement a given measurement pattern. For measurement patterns which have quantum circuit representation as formalized by the notion of flow, with nnn inputs, nnn outputs, and mmm total qubits, we show that only a minimum of n+1n+1n+1 and mmm qubits are required, while the number of required qubits can be as high as m\ensuremath−2m\ensuremath{-}2m\ensuremath−2 for measurement patterns which implement a unitary but do not have a quantum circuit representation, as formalized by the notion of generalized flow (gflow). We discuss the implications of removing the Clifford part of a measurement pattern, using well-established transformation rules for Pauli measurements, for the presence of flow versus gflow, and hence the effect on the minimum number of physical qubits required to directly realize the measurement pattern.
We consider the explicit construction of resource states for measurement-based quantum information processing. We concentrate on special-purpose resource states that are capable to perform a certain operation or task, where we consider unitary Clifford circuits as well as non-trace-preserving completely positive maps, more specifically probabilistic operations including Clifford operations and Pauli measurements. We concentrate on $1\ensuremath{\rightarrow}m$ and $m\ensuremath{\rightarrow}1$ operations, i.e., operations that map one input qubit to mmm output qubits or vice versa. Examples of such operations include encoding and decoding in quantum error correction, entanglement purification, or entanglement swapping. We provide a general framework to construct optimal resource states for complex tasks that are combinations of these elementary building blocks. All resource states only contain input and output qubits, and are hence of minimal size. We obtain a stabilizer description of the resulting resource states, which we also translate into a circuit pattern to experimentally generate these states. In particular, we derive recurrence relations at the level of stabilizers as key analytical tool to generate explicit (graph) descriptions of families of resource states. This allows us to explicitly construct resource states for encoding, decoding, and syndrome readout for concatenated quantum error correction codes, code switchers, multiple rounds of entanglement purification, quantum repeaters, and combinations thereof (such as resource states for entanglement purification of encoded states).
Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.
In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via single-qubit measurements on a resource state.Flow conditions ensure that the overall computation is deterministic in a suitable sense, and are required for efficient translation into quantum circuits.Procedures that rewrite MBQC patterns -e.g. for optimisation, or adapting to hardware constraints -thus need to preserve the existence of flow.Most previous work has focused on rewrites that reduce the number of qubits in the computation, or that introduce new Pauli-measured qubits.Here, we consider the insertion of planar-measured qubits into MBQC patterns, i.e. arbitrary measurements in a plane of the Bloch sphere spanned by a pair of Pauli operators; such measurements are necessary for universal MBQC.We extend the definition of causal flow, previously restricted to XY -measurements only, to also permit Y Z-measurements and derive the conditions under which a Y Z-insertion preserves causal flow.Then we derive conditions for Y Z-insertion into patterns with gflow or Pauli flow, in which case the argument straightforwardly extends to XZ-insertions as well.We also show that the 'vertex splitting' or 'neighbour unfusion' rule previously used in the literature can be derived from Y Z-insertion and pivoting.This work contributes to understanding the broad properties of flow-preserving rewriting in MBQC and in the ZX-calculus more broadly, and it will enable more efficient optimisation, obfuscation, or routing.
In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard resource state.So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these.Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits.In this work, we show that introducing new Z-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow.Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [17].We prove that any MBQClike stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow, and that each of these rules can be reversed while also preserving the existence of Pauli flow.Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.
Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.” In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems. We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.
Abstract We show how to perform measurement-based quantum computing on qudits (high-dimensional quantum systems) using alternative resource states beyond the cluster state. Estimating overheads for gate decomposition, we find that generalizing standard qubit measurement patterns to the qudit cluster state is suboptimal in most dimensions, so that alternative qudit resource states could enable enhanced computational efficiency. In these resources, the entangling interaction is a block-diagonal Clifford operation rather than the usual controlled-phase gate for cluster states. This simple change has remarkable consequences: the applied entangling operation determines an intrinsic single-qudit gate associated with the resource that drives the quantum computation when performing single-qudit measurements on the resource state. We prove a condition for the intrinsic gate allowing for the measurement-based implementation of arbitrary single-qudit unitaries. Furthermore, we demonstrate for prime-power-dimensional qudits that the complexity of the realization depends linearly both on the dimension and the Pauli order of the intrinsic gate. These insights also allow us to optimize the efficiency of the standard qudit cluster state by effectively mimicking more favorable intrinsic-gate structures, thereby reducing the required measurement depth. Finally, we discuss the required two-dimensional geometry of the resource state for universal measurement-based quantum computing. As concrete examples, we present multiple alternative resource states. In certain dimensions, we show the existence of resource states achieving optimal intrinsic gates, enabling more efficient measurement-based quantum information processing than the qudit cluster state and highlighting the potential of qudit stabilizer state resources for future quantum computing architectures.