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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Measurement-Based Quantum Computing as a Tangram Puzzle

Ashlesha Patil, Yosef P. Jacobson, Don Towsley, Saikat Guha

Published Sep 1, 2022• 3 citations
Publisher

Abstract

Measurement-Based Quantum Computing (MBQC), proposed in 2001 is a model of quantum computing that achieves quantum computation by performing a series of adaptive single-qubit measurements on an entangled cluster state. Our project is aimed at introducing MBQC to a wide audience ranging from high school students to quantum computing researchers through a Tangram puzzle with a modified set of rules played on an applet. The player is provided a quantum circuit which they have to map to MBQC using polyominos. Polyominos, the building blocks of our game, consist of square tiles joined edge-to-edge to form different shapes. Each tile represents a measurement basis, differentiated by its color. Polyominos rest on a square-grid playing board, which signifies a cluster state. We show that mapping a quantum circuit to MBQC is equivalent to arranging a set of polyominos—each corresponding to a gate in the circuit—on the playing board, subject to certain rules. We state the rules in simple terms with no reference to quantum computing. One such rule describes ways to deform a polyomino while it still correctly realizes a given quantum gate. The player has to place polyominos on the playing board conforming to the rules. Any correct solution creates a valid realization of the quantum circuit in MBQC. A higher-scoring correct solution fills up less space on the board, resulting in a lower-overhead embedding of the circuit in MBQC, a challenging research problem.

DOI
10.1109/qce53715.2022.00124

Related papers

Measurement-based Quantum Computation as a Tangram Puzzle

Ashlesha Patil, Yosef P. Jacobson, Don Towsley +1 more

Measurement-Based Quantum Computing (MBQC), proposed in 2001 is a model of quantum computing that achieves quantum computation by performing a series of adaptive single-qubit measurements on an entangled cluster state. Our project is aimed at introducing MBQC to a wide audience ranging from high school students to quantum computing researchers through a Tangram puzzle with a modified set of rules, played on an applet. The rules can be understood without any background in quantum computing. The player is provided a quantum circuit, shown using gates from a universal gate set, which the player must map correctly to a playing board using polyominos. Polyominos or 'puzzle blocks' are the building blocks of our game. They consist of square tiles joined edge-to-edge to form different colored shapes. Each tile represents a single-qubit measurement basis, differentiated by its color. Polyominos rest on a square-grid playing board, which signifies a cluster state. We show that mapping a quantum circuit to MBQC is equivalent to arranging a set of polyominos, each corresponding to a gate in the circuit on the playing board, subject to certain rules, which involve rotating and deforming polyominos. We state the rules in simple terms with no reference to quantum computing. The player has to place polyominos on the playing board conforming to the rules. Any correct solution creates a valid realization of the quantum circuit in MBQC. A higher-scoring correct solution fills up less space on the board, resulting in a lower-overhead embedding of the circuit in MBQC, an open and challenging research problem.

arXiv:2210.11465•Oct 20, 2022•0 citations

Measurement-based quantum computation from Clifford quantum cellular automata

Hendrik Poulsen Nautrup, Hans J. Briegel

Measurement-based quantum computation (MBQC) is a paradigm for quantum computation where computation is driven by local measurements on a suitably entangled resource state. In this work we show that MBQC is related to a model of quantum computation based on Clifford quantum cellular automata (CQCAs). Specifically, we show that certain MBQCs can be directly constructed from CQCAs which yields a simple and intuitive circuit model representation of MBQC in terms of quantum computation based on CQCA. We apply this description to construct various MBQC-based Ans\"atze for parametrized quantum circuits, demonstrating that the different Ans\"atze may lead to significantly different performances on different learning tasks. In this way, MBQC yields a family of hardware-efficient Ans\"atze that may be adapted to specific problem settings and are particularly well suited for architectures with translationally invariant gates such as neutral atoms.

arXiv:2312.13185•Physical Review A•Dec 23, 2024•4 citations

Realizations of Measurement Based Quantum Computing

Swapnil Nitin Shah

The Measurement Based Quantum Computation (MBQC) model achieves universal quantum computation by employing projective single qubit measurements with classical feedforward on a highly entangled multipartite cluster state. Rapid advances in improving scalability of quantum computing systems have enabled the generation of large cluster states for implementing MBQC on various platforms. This review focuses on three such efforts, each utilizing a different quantum computing technology viz., superconducting qubits, trapped ion qubits and squeezed photon states. MBQC is being increasingly employed on optical platforms which can generate large entangled resource states but lack the ability to perform deterministic entangling gates.

arXiv:2112.11601•Dec 22, 2021•1 citation

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

Benchmarking the emulation of measurement-based quantum computing through the Max K-Cut algorithm

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

Abstract The measurement-based quantum computing paradigm relies on entangling the qubits of a register into a graph state and on measuring subsets of such register in order to condition the unmeasured qubits. The computation therefore, instead of being carried on only by one-qubit and two-qubits logic gates, is largely based on entanglement and measurement processes. Compared to the gate model architecture, in MBQC the overhead in terms of computation resources to synthesize logical qubits is higher. While gate model relies on a register of logical qubits whose number is set at the beginning of the computation and remains constant during the computation, in the MBQC the input qubits outnumber the output ones, due to the destructive nature of measurement processes. Still, we analytically prove and experimentally confirm that MBQC can be efficiently emulated on a classical software, reaching equal loads with respect to the gate-based approach in terms of average runtime and storage of memory. The numerical results confirm that despite the potential computational overhead due to the high entanglement of the initial graph state, the MBQC paradigm carries similar computational complexity, both in terms of time and memory, with respect to the gate-based approach.

Quantum Information Processing•Dec 11, 2025•2 citations

Noise in one-dimensional measurement-based quantum computing

Naïri Usher, Dan E. Browne

Measurement-Based Quantum Computing (MBQC) is an alternative to the quantum circuit model, whereby the computation proceeds via measurements on an entangled resource state. Noise processes are a major experimental challenge to the construction of a quantum computer. Here, we investigate how noise processes affecting physical states affect the performed computation by considering MBQC on a one-dimensional cluster state. This allows us to break down the computation in a sequence of building blocks and map physical errors to logical errors. Next, we extend the Matrix Product State construction to mixed states (which is known as Matrix Product Operators) and once again map the effect of physical noise to logical noise acting within the correlation space. This approach allows us to consider more general errors than the conventional Pauli errors, and could be used in order to simulate noisy quantum computation.

arXiv:1704.07298•Quantum Information and Computation•Dec 1, 2017•6 citations
Measurement-Based Quantum Computing (MBQC), proposed in 2001 is a model of quantum computing that achieves quantum computation by performing a series of adaptive single-qubit measurements on an entangled cluster state. Our project is aimed at introducing MBQC to a wide audience ranging from high school students to quantum computing researchers through a Tangram puzzle with a modified set of rules played on an applet. The player is provided a quantum circuit which they have to map to MBQC using polyominos. Polyominos, the building blocks of our game, consist of square tiles joined edge-to-edge to form different shapes. Each tile represents a measurement basis, differentiated by its color. Polyominos rest on a square-grid playing board, which signifies a cluster state. We show that mapping a quantum circuit to MBQC is equivalent to arranging a set of polyominos—each corresponding to a gate in the circuit—on the playing board, subject to certain rules. We state the rules in simple terms with no reference to quantum computing. One such rule describes ways to deform a polyomino while it still correctly realizes a given quantum gate. The player has to place polyominos on the playing board conforming to the rules. Any correct solution creates a valid realization of the quantum circuit in MBQC. A higher-scoring correct solution fills up less space on the board, resulting in a lower-overhead embedding of the circuit in MBQC, a challenging research problem.
Measurement-Based Quantum Computing (MBQC), proposed in 2001 is a model of quantum computing that achieves quantum computation by performing a series of adaptive single-qubit measurements on an entangled cluster state. Our project is aimed at introducing MBQC to a wide audience ranging from high school students to quantum computing researchers through a Tangram puzzle with a modified set of rules, played on an applet. The rules can be understood without any background in quantum computing. The player is provided a quantum circuit, shown using gates from a universal gate set, which the player must map correctly to a playing board using polyominos. Polyominos or 'puzzle blocks' are the building blocks of our game. They consist of square tiles joined edge-to-edge to form different colored shapes. Each tile represents a single-qubit measurement basis, differentiated by its color. Polyominos rest on a square-grid playing board, which signifies a cluster state. We show that mapping a quantum circuit to MBQC is equivalent to arranging a set of polyominos, each corresponding to a gate in the circuit on the playing board, subject to certain rules, which involve rotating and deforming polyominos. We state the rules in simple terms with no reference to quantum computing. The player has to place polyominos on the playing board conforming to the rules. Any correct solution creates a valid realization of the quantum circuit in MBQC. A higher-scoring correct solution fills up less space on the board, resulting in a lower-overhead embedding of the circuit in MBQC, an open and challenging research problem.
Measurement-based quantum computation (MBQC) is a paradigm for quantum computation where computation is driven by local measurements on a suitably entangled resource state. In this work we show that MBQC is related to a model of quantum computation based on Clifford quantum cellular automata (CQCAs). Specifically, we show that certain MBQCs can be directly constructed from CQCAs which yields a simple and intuitive circuit model representation of MBQC in terms of quantum computation based on CQCA. We apply this description to construct various MBQC-based Ans\"atze for parametrized quantum circuits, demonstrating that the different Ans\"atze may lead to significantly different performances on different learning tasks. In this way, MBQC yields a family of hardware-efficient Ans\"atze that may be adapted to specific problem settings and are particularly well suited for architectures with translationally invariant gates such as neutral atoms.
The Measurement Based Quantum Computation (MBQC) model achieves universal quantum computation by employing projective single qubit measurements with classical feedforward on a highly entangled multipartite cluster state. Rapid advances in improving scalability of quantum computing systems have enabled the generation of large cluster states for implementing MBQC on various platforms. This review focuses on three such efforts, each utilizing a different quantum computing technology viz., superconducting qubits, trapped ion qubits and squeezed photon states. MBQC is being increasingly employed on optical platforms which can generate large entangled resource states but lack the ability to perform deterministic entangling gates.
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.
Abstract The measurement-based quantum computing paradigm relies on entangling the qubits of a register into a graph state and on measuring subsets of such register in order to condition the unmeasured qubits. The computation therefore, instead of being carried on only by one-qubit and two-qubits logic gates, is largely based on entanglement and measurement processes. Compared to the gate model architecture, in MBQC the overhead in terms of computation resources to synthesize logical qubits is higher. While gate model relies on a register of logical qubits whose number is set at the beginning of the computation and remains constant during the computation, in the MBQC the input qubits outnumber the output ones, due to the destructive nature of measurement processes. Still, we analytically prove and experimentally confirm that MBQC can be efficiently emulated on a classical software, reaching equal loads with respect to the gate-based approach in terms of average runtime and storage of memory. The numerical results confirm that despite the potential computational overhead due to the high entanglement of the initial graph state, the MBQC paradigm carries similar computational complexity, both in terms of time and memory, with respect to the gate-based approach.
Measurement-Based Quantum Computing (MBQC) is an alternative to the quantum circuit model, whereby the computation proceeds via measurements on an entangled resource state. Noise processes are a major experimental challenge to the construction of a quantum computer. Here, we investigate how noise processes affecting physical states affect the performed computation by considering MBQC on a one-dimensional cluster state. This allows us to break down the computation in a sequence of building blocks and map physical errors to logical errors. Next, we extend the Matrix Product State construction to mixed states (which is known as Matrix Product Operators) and once again map the effect of physical noise to logical noise acting within the correlation space. This approach allows us to consider more general errors than the conventional Pauli errors, and could be used in order to simulate noisy quantum computation.