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:2312.16433 · Physical Review Letters

Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation

Yuki Takeuchi

Published Jul 30, 2024• 5 citations
arXivHTMLPDF

Abstract

There are two types of universality in measurement-based quantum computation (MBQC): strict and computational. It is well known that the former is stronger than the latter. We present a method of transforming from a certain type of computationally universal MBQC to a strictly universal one. Our method simply replaces a single qubit in a resource state with a Pauli-Y eigenstate. We applied our method to show that hypergraph states can be made strictly universal with only Pauli measurements, while only computationally universal hypergraph states were known.

DOI
10.1103/physrevlett.133.050601

Related papers

Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements

Yuki Takeuchi, Tomoyuki Morimae, Masahito Hayashi

Measurement-based quantum computing is one of the most promising quantum computing models. Although various universal resource states have been proposed so far, it was open whether only two Pauli bases are enough for both of universal measurement-based quantum computing and its verification. In this paper, we construct a universal hypergraph state that only requires X and Z-basis measurements for universal measurement-based quantum computing. We also show that universal measurement-based quantum computing on our hypergraph state can be verified in polynomial time using only X and Z-basis measurements. Furthermore, in order to demonstrate an advantage of our hypergraph state, we construct a verifiable blind quantum computing protocol that requires only X and Z-basis measurements for the client.

arXiv:1809.07552•Scientific Reports•Sep 19, 2019•58 citations

Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources

Brent Harrison, Vishnu Iyer, Ojas Parekh +2 more

Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.

arXiv:2510.05557•Oct 7, 2025•4 citations

Demonstration of hypergraph-state quantum information processing

Jieshan Huang, Xudong Li, Xiaojiong Chen +7 more

Complex entangled states are the key resources for measurement-based quantum computations, which is realised by performing a sequence of measurements on initially entangled qubits. Executable quantum algorithms in the graph-state quantum computing model are determined by the entanglement structure and the connectivity of entangled qubits. By generalisation from graph-type entanglement in which only the nearest qubits interact to a new type of hypergraph entanglement in which any subset of qubits can be arbitrarily entangled via hyperedges, hypergraph states represent more general resource states that allow arbitrary quantum computation with Pauli universality. Here we report experimental preparation, certification and processing of complete categories of four-qubit hypergraph states under the principle of local unitary equivalence, on a fully reprogrammable silicon-photonic quantum chip. Genuine multipartite entanglement for hypergraph states is certificated by the characterisation of entanglement witness, and the observation of violations of Mermin inequalities without any closure of distance or detection loopholes. A basic measurement-based protocol and an efficient resource state verification by color-encoding stabilizers are implemented with local Pauli measurement to benchmark the building blocks for hypergraph-state quantum computation. Our work prototypes hypergraph entanglement as a general resource for quantum information processing.

Nature Communications•Mar 23, 2024•34 citations

Universal MBQC with generalised parity-phase interactions and Pauli measurements

Aleks Kissinger, John van de Wetering

We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp⁡(−iπ2nZ⊗Z) . When n=2 , these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2 , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2 , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n -th level of the Clifford hierarchy.

arXiv:1704.06504•Quantum•Apr 26, 2019•43 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•76 citations

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

Monireh Houshmand, Mahboobeh Houshmand, Joseph F. Fitzsimons

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.

arXiv:1705.01535•Physical Review A•Jul 17, 2018•14 citations
There are two types of universality in measurement-based quantum computation (MBQC): strict and computational. It is well known that the former is stronger than the latter. We present a method of transforming from a certain type of computationally universal MBQC to a strictly universal one. Our method simply replaces a single qubit in a resource state with a Pauli-Y eigenstate. We applied our method to show that hypergraph states can be made strictly universal with only Pauli measurements, while only computationally universal hypergraph states were known.
Measurement-based quantum computing is one of the most promising quantum computing models. Although various universal resource states have been proposed so far, it was open whether only two Pauli bases are enough for both of universal measurement-based quantum computing and its verification. In this paper, we construct a universal hypergraph state that only requires X and Z-basis measurements for universal measurement-based quantum computing. We also show that universal measurement-based quantum computing on our hypergraph state can be verified in polynomial time using only X and Z-basis measurements. Furthermore, in order to demonstrate an advantage of our hypergraph state, we construct a verifiable blind quantum computing protocol that requires only X and Z-basis measurements for the client.
Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming BQP≠BPP\mathsf{BQP} \neq \mathsf{BPP}BQP=BPP). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.
Complex entangled states are the key resources for measurement-based quantum computations, which is realised by performing a sequence of measurements on initially entangled qubits. Executable quantum algorithms in the graph-state quantum computing model are determined by the entanglement structure and the connectivity of entangled qubits. By generalisation from graph-type entanglement in which only the nearest qubits interact to a new type of hypergraph entanglement in which any subset of qubits can be arbitrarily entangled via hyperedges, hypergraph states represent more general resource states that allow arbitrary quantum computation with Pauli universality. Here we report experimental preparation, certification and processing of complete categories of four-qubit hypergraph states under the principle of local unitary equivalence, on a fully reprogrammable silicon-photonic quantum chip. Genuine multipartite entanglement for hypergraph states is certificated by the characterisation of entanglement witness, and the observation of violations of Mermin inequalities without any closure of distance or detection loopholes. A basic measurement-based protocol and an efficient resource state verification by color-encoding stabilizers are implemented with local Pauli measurement to benchmark the building blocks for hypergraph-state quantum computation. Our work prototypes hypergraph entanglement as a general resource for quantum information processing.
We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp⁡(−iπ2nZ⊗Z) . When n=2 , these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2 , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2 , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n -th level of the Clifford hierarchy.
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.
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{-}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.