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:2306.13372 · International Journal of Quantum Information

Three-qubit Deutsch–Jozsa in measurement-based quantum computing

Maximilian Schwetz, R. M. Noack

Published Dec 4, 2023• 0 citations
arXivHTMLPDF

Abstract

Measurement-based quantum computing (MBQC), an alternate paradigm for formulating quantum algorithms, can lead to potentially more flexible and efficient implementations as well as to theoretical insights on the role of entanglement in a quantum algorithm. Using the graph-theoretical ZX-calculus, we describe and apply a general scheme for reformulating quantum circuits as MBQC implementations. After illustrating the method using the two-qubit Deutsch–Jozsa algorithm, we derive a ZX graph-diagram that encodes a general MBQC implementation for the three-qubit Deutsch–Jozsa algorithm. This graph describes an 11-qubit cluster state on which single-qubit measurements are used to execute the algorithm. Particular sets of choices of the axes for the measurements can be used to implement any realization of the oracle. In addition, we derive an equivalent lattice cluster state for the algorithm.

DOI
10.1142/s0219749923500466

Related papers

Simon algorithm in measurement-based quantum computing

Maximilian Schwetz, R. M. Noack

Simon's hidden subgroup algorithm was the first quantum algorithm to prove the superiority of quantum computing over classical computing in terms of complexity. Measurement-based quantum computing (MBQC) is a formulation of quantum computing that, while equivalent in terms of computational power, can be advantageous in experiments and in displaying the core mechanics of quantum algorithms. We present a reformulation of the Simon algorithm into the language of MBQC -- in detail for two qubits and schematically for $n$ qubits. We utilize the framework of ZX-calculus, a graphical tensor description of quantum states and operators, to translate the circuit description of the algorithm into a form concordant with MBQC. The result for the two-qubit Simon algorithm is a ten-qubit cluster state on which single-qubit measurements suffice to extract the desired information. Additionally, we show that the $n$-qubit version of the Simon algorithm can be formulated in MBQC as cluster state graph with $2n$ nodes and $n^2$ edges. This is an example of the MBQC formulation of a quantum algorithm that is exponentially faster than its classical counterpart. As such, this formulation should aid in understanding the core mechanics of such an established algorithm and could serve as a blueprint for experimental implementation.

arXiv:2405.18143•May 28, 2024•0 citations

Measurement-Based Quantum Computing on a Photonic Chip

Jeldrik Huster, Louis L. Hohmann, Kevin Edelmann +1 more

Integrated photonics provides a scalable platform for quantum information processing. In this context, measurement-based quantum computing (MBQC) offers an attractive approach in which quantum computation is realised by adaptive measurements on highly entangled graph states, circumventing the need for deterministic photon-photon interactions. Here, we demonstrate MBQC on an integrated silicon photonic chip capable of generating photonic graph states with up to four qubits. We achieve fidelities of $F_{Star} = (83.5 \pm 1.8)\,\%$ and $F_{Lin} = (75.6 \pm 1.1)\,\%$ for four-photon star and linear graph states, respectively. We use these resource states to implement MBQC-based single- and two-qubit gates and to demonstrate Grover's search algorithm and the Deutsch-Jozsa algorithm. These results establish the feasibility of reconfigurable four-photon MBQC on an integrated photonic platform and provide a foundation for future larger-scale implementations.

quant-pharXiv:2607.07890•Jul 10, 2026•0 citations

Parallel Quantum Circuit Extraction from MBQC-Patterns

Marcel Quanz, Korbinian Staudacher, Karl Fürlinger

In the model of measurement-based quantum computing (MBQC), computations are performed via sequential measurements on a highly entangled graph state. MBQC is a natural model for photonic quantum computing and has been shown to be useful for tasks like optimization and verification of general quantum computations. Therefore, it is often necessary to translate between MBQC and the predominantly used quantum circuit model in a fast and reliable way. While there are algorithms with linear complexity to extract quantum circuits from measurement patterns using additional ancilla qubits, efficient ancilla-free extraction has shown to be more costly. We develop strategies to parallelize an existing extraction algorithm based on ZX-calculus by exploiting the graph structure of measurement patterns and evaluate the performance on patterns obtained from a benchmark set of quantum circuits. Our results suggest that possible parallelization speedups are closely related to the graph structure of a pattern.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 27, 2024•0 citations

Measurement-based quantum compiling via gauge invariance

Sebastiano Corli, Enrico Prati

The measurement-based architecture is a paradigm of quantum computing, relying on the entanglement of a cluster of qubits and the measurements of a subset of it, conditioning the state of the unmeasured output qubits. While methods to map the gate model circuits into the measurement-based are already available via intermediate steps, we introduce a paradigm for quantum compiling directly converting any quantum circuit to a class of graph states, independently from its size. This method relies on the stabilizer formalism to describe the register of the input qubits. An equivalence class between graph states able to implement the same circuit is defined, giving rise to a gauge freedom when compiling in the MBQC frame. The graph state can be rebuilt from the circuit and the input by employing a set of graphical rules. A system of equations describes the overall process. Compared with measurement calculus, the ancillary qubits are reduced by 50% on the quantum Fourier transform and 75% on the Quantum Approximate Optimization Algorithm, still preserving similar scaling laws for the number of entangling gates.

arXiv:2411.12485•Physical Review Applied•Mar 24, 2026•2 citations

Performing a Quantum Subroutine Using Cluster States

Sakibul Islam Rayhan, Karima Hassan, Md Rasedujjaman +1 more

Quantum subroutines, like their classical counterparts, serve as essential components of larger algorithms. They can be realized using gate based architectures or measurement based quantum computation (MBQC), where computation proceeds through adaptive measurements on highly entangled cluster states. In this work, we implement a phase oracle as a reusable subroutine within the MBQC framework using experimentally feasible cluster states. Unlike prior demonstrations of Grover's algorithm in MBQC that omit explicit oracle construction, our approach provides a transparent formulation of the oracle subroutine, including its measurement patterns, byproduct correlations, density-matrix simulations, and corresponding MBQC measurement circuits.

quant-pharXiv:2610.32227•Oct 26, 2026•0 citations

Programming Non-Trivial Algorithms in the Measurement Based Quantum Computation Model

Paul M. Alsing

We provide a set of prescriptions for implementing a quantum circuit model algorithm as measurement based quantum computing (MBQC) algorithm1, 2 via a large cluster state. As means of illustration we draw upon our numerical modeling experience to describe a large graph state capable of searching a logical 8 element list (a non-trivial version of Grover's algorithm3 with feedforward). We develop several prescriptions based on analytic evaluation of cluster states and graph state equations which can be generalized into any circuit model operations. Such a resulting cluster state will be able to carry out the desired operation with appropriate measurements and feed forward error correction. We also discuss the physical implementation and the analysis of the principal 3-qubit entangling gate (Toffoli) required for a non-trivial feedforward realization of an 8-element Grover search algorithm.

•Aug 11, 2016•0 citations
Measurement-based quantum computing (MBQC), an alternate paradigm for formulating quantum algorithms, can lead to potentially more flexible and efficient implementations as well as to theoretical insights on the role of entanglement in a quantum algorithm. Using the graph-theoretical ZX-calculus, we describe and apply a general scheme for reformulating quantum circuits as MBQC implementations. After illustrating the method using the two-qubit Deutsch–Jozsa algorithm, we derive a ZX graph-diagram that encodes a general MBQC implementation for the three-qubit Deutsch–Jozsa algorithm. This graph describes an 11-qubit cluster state on which single-qubit measurements are used to execute the algorithm. Particular sets of choices of the axes for the measurements can be used to implement any realization of the oracle. In addition, we derive an equivalent lattice cluster state for the algorithm.
Simon's hidden subgroup algorithm was the first quantum algorithm to prove the superiority of quantum computing over classical computing in terms of complexity. Measurement-based quantum computing (MBQC) is a formulation of quantum computing that, while equivalent in terms of computational power, can be advantageous in experiments and in displaying the core mechanics of quantum algorithms. We present a reformulation of the Simon algorithm into the language of MBQC -- in detail for two qubits and schematically for nnn qubits. We utilize the framework of ZX-calculus, a graphical tensor description of quantum states and operators, to translate the circuit description of the algorithm into a form concordant with MBQC. The result for the two-qubit Simon algorithm is a ten-qubit cluster state on which single-qubit measurements suffice to extract the desired information. Additionally, we show that the nnn-qubit version of the Simon algorithm can be formulated in MBQC as cluster state graph with 2n2n2n nodes and n2n^2n2 edges. This is an example of the MBQC formulation of a quantum algorithm that is exponentially faster than its classical counterpart. As such, this formulation should aid in understanding the core mechanics of such an established algorithm and could serve as a blueprint for experimental implementation.
Integrated photonics provides a scalable platform for quantum information processing. In this context, measurement-based quantum computing (MBQC) offers an attractive approach in which quantum computation is realised by adaptive measurements on highly entangled graph states, circumventing the need for deterministic photon-photon interactions. Here, we demonstrate MBQC on an integrated silicon photonic chip capable of generating photonic graph states with up to four qubits. We achieve fidelities of FStar=(83.5±1.8) %F_{Star} = (83.5 \pm 1.8)\,\%FStar​=(83.5±1.8)% and FLin=(75.6±1.1) %F_{Lin} = (75.6 \pm 1.1)\,\%FLin​=(75.6±1.1)% for four-photon star and linear graph states, respectively. We use these resource states to implement MBQC-based single- and two-qubit gates and to demonstrate Grover's search algorithm and the Deutsch-Jozsa algorithm. These results establish the feasibility of reconfigurable four-photon MBQC on an integrated photonic platform and provide a foundation for future larger-scale implementations.
In the model of measurement-based quantum computing (MBQC), computations are performed via sequential measurements on a highly entangled graph state. MBQC is a natural model for photonic quantum computing and has been shown to be useful for tasks like optimization and verification of general quantum computations. Therefore, it is often necessary to translate between MBQC and the predominantly used quantum circuit model in a fast and reliable way. While there are algorithms with linear complexity to extract quantum circuits from measurement patterns using additional ancilla qubits, efficient ancilla-free extraction has shown to be more costly. We develop strategies to parallelize an existing extraction algorithm based on ZX-calculus by exploiting the graph structure of measurement patterns and evaluate the performance on patterns obtained from a benchmark set of quantum circuits. Our results suggest that possible parallelization speedups are closely related to the graph structure of a pattern.
The measurement-based architecture is a paradigm of quantum computing, relying on the entanglement of a cluster of qubits and the measurements of a subset of it, conditioning the state of the unmeasured output qubits. While methods to map the gate model circuits into the measurement-based are already available via intermediate steps, we introduce a paradigm for quantum compiling directly converting any quantum circuit to a class of graph states, independently from its size. This method relies on the stabilizer formalism to describe the register of the input qubits. An equivalence class between graph states able to implement the same circuit is defined, giving rise to a gauge freedom when compiling in the MBQC frame. The graph state can be rebuilt from the circuit and the input by employing a set of graphical rules. A system of equations describes the overall process. Compared with measurement calculus, the ancillary qubits are reduced by 50% on the quantum Fourier transform and 75% on the Quantum Approximate Optimization Algorithm, still preserving similar scaling laws for the number of entangling gates.
Quantum subroutines, like their classical counterparts, serve as essential components of larger algorithms. They can be realized using gate based architectures or measurement based quantum computation (MBQC), where computation proceeds through adaptive measurements on highly entangled cluster states. In this work, we implement a phase oracle as a reusable subroutine within the MBQC framework using experimentally feasible cluster states. Unlike prior demonstrations of Grover's algorithm in MBQC that omit explicit oracle construction, our approach provides a transparent formulation of the oracle subroutine, including its measurement patterns, byproduct correlations, density-matrix simulations, and corresponding MBQC measurement circuits.
We provide a set of prescriptions for implementing a quantum circuit model algorithm as measurement based quantum computing (MBQC) algorithm1, 2 via a large cluster state. As means of illustration we draw upon our numerical modeling experience to describe a large graph state capable of searching a logical 8 element list (a non-trivial version of Grover's algorithm3 with feedforward). We develop several prescriptions based on analytic evaluation of cluster states and graph state equations which can be generalized into any circuit model operations. Such a resulting cluster state will be able to carry out the desired operation with appropriate measurements and feed forward error correction. We also discuss the physical implementation and the analysis of the principal 3-qubit entangling gate (Toffoli) required for a non-trivial feedforward realization of an 8-element Grover search algorithm.