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

Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states

Mariami Gachechiladze, Otfried Gühne, Akimasa Miyake

Published May 2, 2019• 39 citations
arXivHTMLPDF

Abstract

While the circuit model of quantum computation defines its logical depth or ``computational time'' in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multiqubit hypergraph states generated by the controlled-controlled-Z (ccz) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of ccz and swap gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an $N$-times controlled-Z gate illustrates a trade-off between space and time complexity.

DOI
10.1103/physreva.99.052304

Related papers

Low depth measurement-based quantum computation beyond two-level systems

Timothy J Proctor

Low depth measurement-based quantum computation with qudits ($d$-level systems) is investigated and a precise relationship between this powerful model and qudit quantum circuits is derived in terms of computational depth and size complexity. To facilitate this investigation a qudit `unbounded fan-out' circuit model, in which a qudit may be quantum-copied into an arbitrary number of ancillas in a single time-step, is introduced and shown to be capable of implementing interesting $n$-qudit unitaries in constant depth. A procedure for reducing the quantum computational depth in the measurement-based model is then proposed and using this it is then shown that there is a logarithmic depth separation between the depth complexity of qudit measurement-based computation and circuits composed of gates act on a bounded number of qudits. The relationship is made precise by showing that the depth complexity of the qudit measurement-based model is exactly equivalent to that of unbounded fan-out circuits. These results illustrate that the well-known advantages inherent in qubit measurement-based quantum computation are also applicable to the higher-dimensional generalisation. As qudits are both naturally available and have been shown to provide fundamental advantages over binary logic encodings, this then suggests that the qudit measurement-based model is a particularly appealing paradigm for universal quantum computation.

arXiv:1510.06472•Oct 22, 2015•2 citations

Reducing depth and measurement weights in Pauli-based computation

Filipa C. R. Peres, Ernesto F. Galvão

Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several techniques for reducing the weight of the Pauli measurements and their associated cnot complexity; we also demonstrate how to decrease this model's computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a precompilation step. We also propose a heuristic algorithm that can contribute to reductions of over 30% to the average weight of Pauli measurements (and associated cnot count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 $T$ gates and over 20% for instances with larger $T$ counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the cnot count by 18% to 96% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger $T$ counts, it leads to a number of cnots roughly 30% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.

arXiv:2408.04007•Physical Review A•Nov 3, 2025•0 citations

Analysis of the trade-off between spatial and temporal resources for measurement-based quantum computation

Jisho Miyazaki, Michal Hajdušek, Mio Murao

In measurement-based quantum computation (MBQC), elementary quantum operations can be more parallelized than the quantum circuit model by employing a larger Hilbert space of graph states used as the resource. Thus MBQC can be regarded as a method of quantum computation where the temporal resource described by the depth of quantum operations can be reduced compared to the quantum circuit model by using the extra spatial resource described by graph states. To analyze the trade-off relationship of the spatial and temporal resources, we consider a method to obtain quantum circuit decompositions of general unitary transformations represented by MBQC on graph states with a certain underlying geometry called generalized flow. We present a method to translate any MBQC with generalized flow into quantum circuits without extra spatial resource. We also show an explicit way to unravel acausal gates without postselection that appear in the quantum circuit decomposition derived by a translation method [V. Danos and E. Kashefi, Phys. Rev. A 74, 052310 (2006)] and that represents an effect of the reduction of the temporal resource in MBQC. Finally, by considering a way to deterministically simulate these acausal gates, we investigate a general framework to analyze the trade-off between the spatial and temporal resources for quantum computation.

arXiv:1310.4043•Physical Review A•May 4, 2015•16 citations

Verification of hypergraph states

Tomoyuki Morimae, Yuki Takeuchi, Masahito Hayashi

Hypergraph states are generalizations of graph states where controlled-$Z$ gates on edges are replaced with generalized controlled-$Z$ gates on hyperedges. Hypergraph states have several advantages over graph states. For example, certain hypergraph states, such as the Union Jack states, are universal resource states for measurement-based quantum computing with only Pauli measurements, while graph state measurement-based quantum computing needs non-Clifford basis measurements. Furthermore, it is impossible to classically efficiently sample measurement results on hypergraph states unless the polynomial hierarchy collapses to the third level. Although several protocols have been proposed to verify graph states with only sequential single-qubit Pauli measurements, there was no verification method for hypergraph states. In this paper, we propose a method for verifying a certain class of hypergraph states with only sequential single-qubit Pauli measurements. Importantly, no i.i.d. property of samples is assumed in our protocol: any artificial entanglement among samples cannot fool the verifier. As applications of our protocol, we consider verified blind quantum computing with hypergraph states, and quantum computational supremacy demonstrations with hypergraph states.

arXiv:1701.05688•Physical Review A•Dec 20, 2017•63 citations

Mapping quantum circuits to shallow-depth measurement patters based on graph states

Kaldenbach, Thierry Nicolas, Heller, Matthias

The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions—a so-called standard for —which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus, enabling a significant decrease in circuit depth for certain applications. We show that groups of mutually-commuting operators can be implemented using fully-parallel, i.e. non-adaptive, measurements within our protocol. In addition, we discuss how groups of mutually commuting observables can be simulatenously measured by adjusting the resource state, rather than performing a costly basis transformation prior to the measurement as it is done in the circuit model. Finally, we demonstrate the utility of our technique on two examples of high practical relevance—the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver (VQE) for the ground-state energy estimation of the water molecule. For the VQE, we find a reduction of the depth by a factor of 4 to 5 using measurement patterns vs. the standard circuit model. At the same time, since we incorporate the simultaneous measurements, our patterns allow us to save shots by a factor of at least 3.5 compared to measuring Pauli strings individually in the circuit model.

•Mar 1, 2024•0 citations

Non-Clifford symmetry protected topological hyper-cluster states and multi-qubit universal measurement-based quantum computation

Motohiko Ezawa

A cluster state is a highly entangled quantum state that serves as a universal resource for measurement-based quantum computation. It is generated by applying controlled-Z (CZ) gates to the product state $\left\vert ++\cdots +\right\rangle $, and its parent Hamiltonian is the ZXZ model. This model exhibits a topological phase protected by the $\mathbb{Z}_{2}^{\text{even}}\times \mathbb{Z}_{2}^{\text{odd}}$\ symmetry. By applying general quantum gates to the state $\left\vert ++\cdots +\right\rangle $, we systematically obtain a general short-range entangled cluster state. If we use the controlled-controlled Z (CCZ) gate instead of the CZ gate, we obtain hyper-cluster states featuring five-body interaction terms. These states enable the implementation of the CZ gate within measurement-based quantum computation. Motivated by this, we propose a generalization to the C$^{N}$Z gate, leading to a hyper-cluster model, in which $(2N+1)$-body entangled states are generated. This model retains the $\mathbb{Z}_{2}^{\text{even}}\times \mathbb{Z}_{2}^{\text{odd}}$\ symmetry, which lies outside the Clifford group for $N\geq 3$. We demonstrate that an open chain in this model exhibits a $2^{2N}$ fold degenerate ground states protected by the symmetry, corresponding to the emergence of $N$ effective free spins at each edge. These boundary degrees of freedom can serve as $N$ qubits for measurement-based quantum computation. In particular, this framework makes it possible to implement the C$^{N-1}$Z gate in measurement-based quantum computation.

quant-pharXiv:2602.20612•Feb 25, 2026•0 citations
While the circuit model of quantum computation defines its logical depth or ``computational time'' in terms of temporal gate sequences, the measurement-based model could allow totally different temporal ordering and parallelization of logical gates. By developing techniques to analyze Pauli measurements on multiqubit hypergraph states generated by the controlled-controlled-Z (ccz) gates, we introduce a deterministic scheme of universal measurement-based computation. In contrast to the cluster-state scheme where the Clifford gates are parallelizable, our scheme enjoys massive parallelization of ccz and swap gates, so that the computational depth grows with the number of global applications of Hadamard gates, or, in other words, with the number of changing computational bases. A logarithmic-depth implementation of an NNN-times controlled-Z gate illustrates a trade-off between space and time complexity.
Low depth measurement-based quantum computation with qudits (ddd-level systems) is investigated and a precise relationship between this powerful model and qudit quantum circuits is derived in terms of computational depth and size complexity. To facilitate this investigation a qudit `unbounded fan-out' circuit model, in which a qudit may be quantum-copied into an arbitrary number of ancillas in a single time-step, is introduced and shown to be capable of implementing interesting nnn-qudit unitaries in constant depth. A procedure for reducing the quantum computational depth in the measurement-based model is then proposed and using this it is then shown that there is a logarithmic depth separation between the depth complexity of qudit measurement-based computation and circuits composed of gates act on a bounded number of qudits. The relationship is made precise by showing that the depth complexity of the qudit measurement-based model is exactly equivalent to that of unbounded fan-out circuits. These results illustrate that the well-known advantages inherent in qubit measurement-based quantum computation are also applicable to the higher-dimensional generalisation. As qudits are both naturally available and have been shown to provide fundamental advantages over binary logic encodings, this then suggests that the qudit measurement-based model is a particularly appealing paradigm for universal quantum computation.
Pauli-based computation (PBC) is a universal measurement-based quantum computation model steered by an adaptive sequence of independent and compatible Pauli measurements on separable magic-state qubits. Here, we propose several techniques for reducing the weight of the Pauli measurements and their associated cnot complexity; we also demonstrate how to decrease this model's computational depth. We start by proving new upper bounds on the required weights and computational depth, obtained via a precompilation step. We also propose a heuristic algorithm that can contribute to reductions of over 30% to the average weight of Pauli measurements (and associated cnot count) when simulating and compiling Clifford-dominated random quantum circuits with up to 22 TTT gates and over 20% for instances with larger TTT counts. This PBC-compilation scheme, boosted by the heuristic algorithm, outperforms state-of-the-art compilers for the former circuits, reducing the cnot count by 18% to 96% compared with the values achieved by other techniques. In contrast, for the latter circuits with larger TTT counts, it leads to a number of cnots roughly 30% larger. Finally, inspired by known state-transfer methods, we introduce incPBC, a universal model for quantum computation requiring a larger number of (now incompatible) Pauli measurements of weight at most 2.
In measurement-based quantum computation (MBQC), elementary quantum operations can be more parallelized than the quantum circuit model by employing a larger Hilbert space of graph states used as the resource. Thus MBQC can be regarded as a method of quantum computation where the temporal resource described by the depth of quantum operations can be reduced compared to the quantum circuit model by using the extra spatial resource described by graph states. To analyze the trade-off relationship of the spatial and temporal resources, we consider a method to obtain quantum circuit decompositions of general unitary transformations represented by MBQC on graph states with a certain underlying geometry called generalized flow. We present a method to translate any MBQC with generalized flow into quantum circuits without extra spatial resource. We also show an explicit way to unravel acausal gates without postselection that appear in the quantum circuit decomposition derived by a translation method [V. Danos and E. Kashefi, Phys. Rev. A 74, 052310 (2006)] and that represents an effect of the reduction of the temporal resource in MBQC. Finally, by considering a way to deterministically simulate these acausal gates, we investigate a general framework to analyze the trade-off between the spatial and temporal resources for quantum computation.
Hypergraph states are generalizations of graph states where controlled-ZZZ gates on edges are replaced with generalized controlled-ZZZ gates on hyperedges. Hypergraph states have several advantages over graph states. For example, certain hypergraph states, such as the Union Jack states, are universal resource states for measurement-based quantum computing with only Pauli measurements, while graph state measurement-based quantum computing needs non-Clifford basis measurements. Furthermore, it is impossible to classically efficiently sample measurement results on hypergraph states unless the polynomial hierarchy collapses to the third level. Although several protocols have been proposed to verify graph states with only sequential single-qubit Pauli measurements, there was no verification method for hypergraph states. In this paper, we propose a method for verifying a certain class of hypergraph states with only sequential single-qubit Pauli measurements. Importantly, no i.i.d. property of samples is assumed in our protocol: any artificial entanglement among samples cannot fool the verifier. As applications of our protocol, we consider verified blind quantum computing with hypergraph states, and quantum computational supremacy demonstrations with hypergraph states.
The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions—a so-called standard for —which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus, enabling a significant decrease in circuit depth for certain applications. We show that groups of mutually-commuting operators can be implemented using fully-parallel, i.e. non-adaptive, measurements within our protocol. In addition, we discuss how groups of mutually commuting observables can be simulatenously measured by adjusting the resource state, rather than performing a costly basis transformation prior to the measurement as it is done in the circuit model. Finally, we demonstrate the utility of our technique on two examples of high practical relevance—the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver (VQE) for the ground-state energy estimation of the water molecule. For the VQE, we find a reduction of the depth by a factor of 4 to 5 using measurement patterns vs. the standard circuit model. At the same time, since we incorporate the simultaneous measurements, our patterns allow us to save shots by a factor of at least 3.5 compared to measuring Pauli strings individually in the circuit model.
A cluster state is a highly entangled quantum state that serves as a universal resource for measurement-based quantum computation. It is generated by applying controlled-Z (CZ) gates to the product state $\left\vert ++\cdots +\right\rangle $, and its parent Hamiltonian is the ZXZ model. This model exhibits a topological phase protected by the Z2even×Z2odd\mathbb{Z}_{2}^{\text{even}}\times \mathbb{Z}_{2}^{\text{odd}}Z2even​×Z2odd​\ symmetry. By applying general quantum gates to the state $\left\vert ++\cdots +\right\rangle ,wesystematicallyobtainageneralshort−rangeentangledclusterstate.Ifweusethecontrolled−controlledZ(CCZ)gateinsteadoftheCZgate,weobtainhyper−clusterstatesfeaturingfive−bodyinteractionterms.ThesestatesenabletheimplementationoftheCZgatewithinmeasurement−basedquantumcomputation.Motivatedbythis,weproposeageneralizationtotheC, we systematically obtain a general short-range entangled cluster state. If we use the controlled-controlled Z (CCZ) gate instead of the CZ gate, we obtain hyper-cluster states featuring five-body interaction terms. These states enable the implementation of the CZ gate within measurement-based quantum computation. Motivated by this, we propose a generalization to the C,wesystematicallyobtainageneralshort−rangeentangledclusterstate.Ifweusethecontrolled−controlledZ(CCZ)gateinsteadoftheCZgate,weobtainhyper−clusterstatesfeaturingfive−bodyinteractionterms.ThesestatesenabletheimplementationoftheCZgatewithinmeasurement−basedquantumcomputation.Motivatedbythis,weproposeageneralizationtotheC^{N}$Z gate, leading to a hyper-cluster model, in which (2N+1)(2N+1)(2N+1)-body entangled states are generated. This model retains the Z2even×Z2odd\mathbb{Z}_{2}^{\text{even}}\times \mathbb{Z}_{2}^{\text{odd}}Z2even​×Z2odd​\ symmetry, which lies outside the Clifford group for N≥3N\geq 3N≥3. We demonstrate that an open chain in this model exhibits a 22N2^{2N}22N fold degenerate ground states protected by the symmetry, corresponding to the emergence of NNN effective free spins at each edge. These boundary degrees of freedom can serve as NNN qubits for measurement-based quantum computation. In particular, this framework makes it possible to implement the CN−1^{N-1}N−1Z gate in measurement-based quantum computation.