Graph states are an elegant and powerful quantum resource for measurement based quantum computation (MBQC). They are also used for many quantum protocols (error correction, secret sharing, etc.). The main focus of this paper is to provide a structural characterization of the graph states that can be used for quantum information processing. The existence of a gflow (generalized flow) is known to be a requirement for open graphs (graph, input set and output set) to perform uniformly and strongly deterministic computations. We weaken the gflow conditions to define two new more general types of MBQC: uniform equiprobability and constant probability. These classes can be useful from a cryptographic and information point of view because even though we can not do a deterministic computation in general we can preserve the information and transfer it perfectly from the inputs to the outputs. We derive simple graph characterizations for these classes and prove that the deterministic and uniform equiprobability classes collapse when the cardinalities of inputs and outputs are the same. We also prove the reversibility of gflow in that case. The new graphical characterizations allow us to go from open graphs to graphs in general and to consider this question: given a graph with no inputs or outputs fixed, which vertices can be chosen as input and output for quantum information processing? We present a characterization of the sets of possible inputs and ouputs for the equiprobability class, which is also valid for deterministic computations with inputs and ouputs of the same cardinality.
Graph states are an elegant and powerful quantum resource for measurement based quantum computation (MBQC). They are also used for many quantum protocols (error correction, secret sharing, etc.). The main focus of this paper is to provide a structural characterization of the graph states that can be used for quantum information processing. The existence of a gflow (generalized flow) is known to be a requirement for open graphs (graph, input set and output set) to perform uniformly and strongly deterministic computations. We weaken the gflow conditions to define two new more general types of MBQC: uniform equiprobability and constant probability. These classes can be useful from a cryptographic and information point of view because even though we can not do a deterministic computation in general we can preserve the information and transfer it perfectly from the inputs to the outputs. We derive simple graph characterizations for these classes and prove that the deterministic and uniform equiprobability classes collapse when the cardinalities of inputs and outputs are the same. We also prove the reversibility of gflow in that case. The new graphical characterizations allow us to go from open graphs to graphs in general and to consider this question: given a graph with no inputs or outputs fixed, which vertices can be chosen as input and output for quantum information processing? We present a characterization of the sets of possible inputs and ouputs for the equiprobability class, which is also valid for deterministic computations with inputs and ouputs of the same cardinality.
The entangled graph states have emerged as an elegant and powerful quantum resource, indeed almost all multiparty protocols can be written in terms of graph states including measurement based quantum computation (MBQC), error correction and secret sharing amongst others. In addition they are at the forefront in terms of implementations. As such they represent an excellent opportunity to move towards integrated protocols involving many of these elements. In this paper we look at expressing and extending graph state secret sharing and MBQC in a common framework and graphical language related to flow. We do so with two main contributions. First we express in entirely graphical terms which set of players can access which information in graph state secret sharing protocols. These succinct graphical descriptions of access allow us to take known results from graph theory to make statements on the generalisation of the previous schemes to present new secret sharing protocols. Second, we give a set of necessary conditions as to when a graph with flow, i.e. capable of performing a class of unitary operations, can be extended to include vertices which can be ignored, pointless measurements, and hence considered as unauthorised players in terms of secret sharing, or error qubits in terms of fault tolerance. This offers a way to extend existing MBQC patterns to secret sharing protocols. Our characterisation of pointless measurements is believed also to be a useful tool for further integrated measurement based schemes, for example in constructing fault tolerant MBQC schemes.
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 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), 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.
We extend the notion of quantum information flow defined by Danos and Kashefi (2006 Phys. Rev. A 74 052310) for the one-way model (Raussendorf and Briegel 2001 Phys. Rev. Lett. 86 910) and present a necessary and sufficient condition for the stepwise uniformly deterministic computation in this model. The generalized flow also applied in the extended model with measurements in the ( X , Y ), ( X , Z ) and ( Y , Z ) planes. We apply both measurement calculus and the stabiliser formalism to derive our main theorem which for the first time gives a full characterization of the stepwise uniformly deterministic computation in the one-way model. We present several examples to show how our result improves over the traditional notion of flow, such as geometries (entanglement graph with input and output) with no flow but having generalized flow and we discuss how they lead to an optimal implementation of the unitaries. More importantly one can also obtain a better quantum computation depth with the generalized flow rather than with flow. We believe our characterization result is particularly valuable for the study of the algorithms and complexity in the one-way model.
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.
One-way quantum computation, or measurement-based quantum computation, is a universal model of quantum computation alternative to the circuit model. The computation progresses by measurements of a pre-prepared resource state together with corrections of undesired outcomes via applications of Pauli gates to yet unmeasured qubits. The fundamental question of this model is determining whether computation can be implemented deterministically. Pauli flow is one of the most general structures guaranteeing determinism. It is also essential for polynomial time ancilla-free circuit extraction. It is known how to efficiently determine the existence of Pauli flow given an open graph together with a measurement labelling (a choice of measurements to be performed). In this work, we focus on the problem of deciding the existence of Pauli flow for a given open graph when the measurement labelling is unknown. We show that this problem is in RP by providing a random polynomial time algorithm. To do it, we extend previous algebraic interpretations of Pauli flow, by showing that, in the case of X and Z measurements only, flow existence corresponds to the right-invertibility of a matrix derived from the adjacency matrix. We also use this interpretation to show that the number of output qubits can always be reduced to match the number of input qubits while preserving the existence of flow.
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)-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) operations to complete.