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

Quantum Information and Computation

Optimising the information flow of one-way quantum computations

Einar Pius, Raphael Dias da Silva, Elham Kashefi

Published Jul 1, 2015• 0 citations
Publisher

Abstract

In the one-way quantum computing model, the information processing is driven by measurements performed on an entangled state, called the resource state. In order to achieve parallelism, one aims to increase the number of simultaneous measurements, such that the effects of decoherence on the resource state are minimised due to the reduction of the time required to run the computation. At the heart of this question is the notion of quantum information flow, which specifies the dependency relations between the measurements in the computations. There exist two well-known techniques for reducing the time required to perform a one-way quantum computation without changing its semantics. The first one, called signal-shifting, transforms the flow of a graph (representing the resource state) within the measurement calculus formalism, whereas the second one, namely finding the maximally-delayed generalised flow, explores the geometry of the graph to increase the number of operations that can be performed simultaneously. In this paper, we show for the first time how these two techniques relate to each other. We prove that the application of the signal-shifting rules to a measurement pattern with flow results in a generalised flow for the pattern. Then, we prove that in the particular case when the input size equals the output size, the gflow obtained using signal-shifting has the lowest possible depth. As a side result, we construct an $O(n^3)$-algorithm for finding maximally delayed gflows on graphs with flow. For those graphs, our algorithm is more efficient than the best previously known algorithm for the same task, which takes $O(n^4)$ operations to complete.

DOI
10.26421/qic15.9-10-6

Related papers

Global Quantum Circuit Optimization

Raphael Dias da Silva, Einar Pius, Elham Kashefi

One of the main goals in quantum circuit optimisation is to reduce the number of ancillary qubits and the depth of computation, to obtain robust computation. However, most of known techniques, based on local rewriting rules, for parallelising quantum circuits will require the addition of ancilla qubits, leading to an undesired space-time tradeoff. Recently several novel approaches based on measurement-based quantum computation (MBQC) techniques attempted to resolve this problem. The key element is to explore the global structure of a given circuit, defined via translation into a corresponding MBQC pattern. It is known that the parallel power of MBQC is superior to the quantum circuit model, and hence in these approaches one could apply the MBQC depth optimisation techniques to achieve a lower depth. However, currently, once the obtained parallel pattern is translated back to a quantum circuit, one should either increase the depth or add ancilla qubits. In this paper we characterise those computations where both optimisation could be achieved together. In doing so we present a new connection between two MBQC depth optimisation procedures, known as the maximally delayed generalised flow and signal shifting. This structural link will allow us to apply an MBQC qubit optimisation procedure known as compactification to a large class of pattern including all those obtained from any arbitrary quantum circuit. We also present a more efficient algorithm (compared to the existing one) for finding the maximally delayed generalised flow for graph states with flow.

arXiv:1301.0351•Jan 2, 2013•17 citations

Finding gflow on unlabelled open graphs

Miriam Backens, Victor Gasse, Piotr Mitosek +1 more

The one-way model of measurement-based quantum computing implements computations via successive adaptive single-qubit measurements on a resource graph state. This model has practical applications, particularly in photonics, and it is also useful as a theoretical tool e.g. for optimisation. Gflow is a necessary and sufficient condition for implementing certain one-way computations deterministically (in a suitable sense); it is also used in efficient translations from the one-way model to quantum circuits. For a computation on $n$ qubits, a gflow can be found in $\mathcal{O}(n^3)$ time. Here, we consider an incompletely specified computation given by an unlabelled open graph: the graph state as well as the input and output qubits are known, but the measurements have not yet been fixed. We give an algorithm that identifies a measurement labelling and a compatible gflow, and runs in $\mathcal{O}(n^3)$, strictly generalising the previous approach. The new algorithm can also handle restrictions on the order of the measurements and returns only solutions compatible with these constraints. We additionally prove that if an open graph has equal numbers of inputs and outputs, it has at most one labelling compatible with gflow; and show how to identify additional inputs for an open graph that does not yet have the maximal number, without breaking an existing gflow.

quant-pharXiv:2609.40099•Oct 1, 2026•0 citations

Parallel quantum computing: from theory to practice

Einar Pius

The term quantum parallelism is commonly used to refer to a property of quantum computations where an algorithm can act simultaneously on a superposition of states. However, this is not the only aspect of parallelism in quantum computing. Analogously to the classical computing model, every algorithm consists of elementary quantum operations and the application of them could be parallelised itself. This kind of parallelism is explored in this thesis in the one way quantum computing (1WQC) and the quantum circuit model. In the quantum circuit model we explore arithmetic circuits and circuit complexity theory. Two new arithmetic circuits for quantum computers are introduced in this work: an adder and a multiply-adder. The latter is especially interesting because its depth (i.e. the number of parallel steps required to finish the computation) is smaller than for any known classical circuit when applied sequentially. From the complexity theoretical perspective we concentrate on the classes QAC0 and QAC0[2], the quantum counterparts of AC0 and AC0[2]. The class AC0 comprises of constant depth circuits with unbounded fan-in AND and OR gates and AC0[2] is obtained when unbounded fan-in parity gates are added to AC0 circuits. We prove that QAC0 circuits with two layers of multi-qubit gates cannot compute parity exactly. This is a step towards proving QAC0 6= QAC0[2], a relation known to hold for AC0 and AC0[2]. In 1WQC, computation is done through measurements on an entangled state called the resource state. Two well known parallelisation methods exist in this model: signal shifting and finding the maximally delayed general flow. The first one uses the measurement calculus formalism to rewrite the dependencies of an existing computation, whereas the second technique exploits the geometry of the resource state to find the optimal ordering of measurements. We prove that the aforementioned methods result in same depth computations when the input and output sizes are equal. Through showing this equivalence we reveal new properties of 1WQC computations and design a new algorithm for the above mentioned parallelisations.

•Jul 1, 2015•1 citation

Geometry-based signal shifting of one-way quantum computation measurement patterns

Maryam Eslamy, Mahboobeh Houshmand, Morteza Saheb Zamani +1 more

In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.

Iranian Conference on Electrical Engineering•May 1, 2016•3 citations

Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements

Mehdi Mhalla, Simon Perdrix, Luc Sanselme

We introduce a new characterisation of determinism in Measurement-Based Quantum Computing (MBQC). The one-way model consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such a correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements, and guarantees robust determinism, however, it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven iff it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.

arXiv:2207.09368•Quantum•Jul 16, 2026•1 citation

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•11 citations
In the one-way quantum computing model, the information processing is driven by measurements performed on an entangled state, called the resource state. In order to achieve parallelism, one aims to increase the number of simultaneous measurements, such that the effects of decoherence on the resource state are minimised due to the reduction of the time required to run the computation. At the heart of this question is the notion of quantum information flow, which specifies the dependency relations between the measurements in the computations. There exist two well-known techniques for reducing the time required to perform a one-way quantum computation without changing its semantics. The first one, called signal-shifting, transforms the flow of a graph (representing the resource state) within the measurement calculus formalism, whereas the second one, namely finding the maximally-delayed generalised flow, explores the geometry of the graph to increase the number of operations that can be performed simultaneously. In this paper, we show for the first time how these two techniques relate to each other. We prove that the application of the signal-shifting rules to a measurement pattern with flow results in a generalised flow for the pattern. Then, we prove that in the particular case when the input size equals the output size, the gflow obtained using signal-shifting has the lowest possible depth. As a side result, we construct an O(n3)O(n^3)O(n3)-algorithm for finding maximally delayed gflows on graphs with flow. For those graphs, our algorithm is more efficient than the best previously known algorithm for the same task, which takes O(n4)O(n^4)O(n4) operations to complete.
One of the main goals in quantum circuit optimisation is to reduce the number of ancillary qubits and the depth of computation, to obtain robust computation. However, most of known techniques, based on local rewriting rules, for parallelising quantum circuits will require the addition of ancilla qubits, leading to an undesired space-time tradeoff. Recently several novel approaches based on measurement-based quantum computation (MBQC) techniques attempted to resolve this problem. The key element is to explore the global structure of a given circuit, defined via translation into a corresponding MBQC pattern. It is known that the parallel power of MBQC is superior to the quantum circuit model, and hence in these approaches one could apply the MBQC depth optimisation techniques to achieve a lower depth. However, currently, once the obtained parallel pattern is translated back to a quantum circuit, one should either increase the depth or add ancilla qubits. In this paper we characterise those computations where both optimisation could be achieved together. In doing so we present a new connection between two MBQC depth optimisation procedures, known as the maximally delayed generalised flow and signal shifting. This structural link will allow us to apply an MBQC qubit optimisation procedure known as compactification to a large class of pattern including all those obtained from any arbitrary quantum circuit. We also present a more efficient algorithm (compared to the existing one) for finding the maximally delayed generalised flow for graph states with flow.
The one-way model of measurement-based quantum computing implements computations via successive adaptive single-qubit measurements on a resource graph state. This model has practical applications, particularly in photonics, and it is also useful as a theoretical tool e.g. for optimisation. Gflow is a necessary and sufficient condition for implementing certain one-way computations deterministically (in a suitable sense); it is also used in efficient translations from the one-way model to quantum circuits. For a computation on nnn qubits, a gflow can be found in O(n3)\mathcal{O}(n^3)O(n3) time. Here, we consider an incompletely specified computation given by an unlabelled open graph: the graph state as well as the input and output qubits are known, but the measurements have not yet been fixed. We give an algorithm that identifies a measurement labelling and a compatible gflow, and runs in O(n3)\mathcal{O}(n^3)O(n3), strictly generalising the previous approach. The new algorithm can also handle restrictions on the order of the measurements and returns only solutions compatible with these constraints. We additionally prove that if an open graph has equal numbers of inputs and outputs, it has at most one labelling compatible with gflow; and show how to identify additional inputs for an open graph that does not yet have the maximal number, without breaking an existing gflow.
The term quantum parallelism is commonly used to refer to a property of quantum computations where an algorithm can act simultaneously on a superposition of states. However, this is not the only aspect of parallelism in quantum computing. Analogously to the classical computing model, every algorithm consists of elementary quantum operations and the application of them could be parallelised itself. This kind of parallelism is explored in this thesis in the one way quantum computing (1WQC) and the quantum circuit model. In the quantum circuit model we explore arithmetic circuits and circuit complexity theory. Two new arithmetic circuits for quantum computers are introduced in this work: an adder and a multiply-adder. The latter is especially interesting because its depth (i.e. the number of parallel steps required to finish the computation) is smaller than for any known classical circuit when applied sequentially. From the complexity theoretical perspective we concentrate on the classes QAC0 and QAC0[2], the quantum counterparts of AC0 and AC0[2]. The class AC0 comprises of constant depth circuits with unbounded fan-in AND and OR gates and AC0[2] is obtained when unbounded fan-in parity gates are added to AC0 circuits. We prove that QAC0 circuits with two layers of multi-qubit gates cannot compute parity exactly. This is a step towards proving QAC0 6= QAC0[2], a relation known to hold for AC0 and AC0[2]. In 1WQC, computation is done through measurements on an entangled state called the resource state. Two well known parallelisation methods exist in this model: signal shifting and finding the maximally delayed general flow. The first one uses the measurement calculus formalism to rewrite the dependencies of an existing computation, whereas the second technique exploits the geometry of the resource state to find the optimal ordering of measurements. We prove that the aforementioned methods result in same depth computations when the input and output sizes are equal. Through showing this equivalence we reveal new properties of 1WQC computations and design a new algorithm for the above mentioned parallelisations.
In one-way quantum computation (1WQC) model, an initial highly entangled state called a graph state is used to perform universal quantum computations by a sequence of adaptive single-qubit measurements and post-measurement Pauli-X and Pauli-Z corrections. The needed computations are organized as measurement patterns or simply patterns in the 1WQC model. The entanglement operations in a pattern can be shown by a graph which together with the set of its input and output qubits is called the geometry of the pattern. Causal flow is a sufficient condition to identify a dependency structure for measurement sequences in order to obtain determinism. Signal shifting is an optimization technique which uses a set of rewrite rules to propagate the Pauli-Z corrections on the measured qubits to the end of patterns. However, automatically applying these rules has difficulties for implementation and is time consuming due to using many ineffective commutation rules. To overcome this problem, in this paper, a new automatic approach is proposed to perform signal shifting on patterns with flows based on their geometries instead of using rewriting rules. It is shown that the time complexity of the proposed approach is improved compared to the previous ones.
We introduce a new characterisation of determinism in Measurement-Based Quantum Computing (MBQC). The one-way model consists in performing local measurements over a large entangled state represented by a graph. The ability to perform an overall deterministic computation requires a correction strategy because of the non-determinism of each measurement. The existence of such a correction strategy depends on the underlying open graph, which is a description of the resource state together with the basis of the performed measurements. GFlow is a well-known graphical characterisation of robust determinism in MBQC when every measurement is performed in some specific planes of the Bloch sphere. While Pauli measurements are ubiquitous in MBQC, GFlow fails to be necessary for determinism when a measurement-based quantum computation involves Pauli measurements. Pauli Flow was designed as a generalisation of GFlow to handle MBQC with Pauli measurements, and guarantees robust determinism, however, it has been shown more recently that it fails to be a necessary condition. Our contribution is twofold. First, we demonstrate that Pauli flow is actually necessary for robust determinism in a weaker sense: given an open graph, i.e. a resource state, a deterministic computation can be driven iff it has a Pauli flow. However, the Pauli flows do not reflect all the possible correction strategies over a particular resource state, and properties like measurement order or computational depth are not necessarily reflected by a Pauli flow. Thus, to characterise determinism in full generality, we introduce a further extension called Shadow Pauli Flow that we prove necessary and sufficient for robust determinism: An MBQC is robustly deterministic if and only if its correction strategy is consistent with a Shadow Pauli flow. Furthermore, we show that Shadow Pauli flow can be computed in polynomial time.
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.