arXiv:2609.40099
Finding gflow on unlabelled open graphs
Miriam Backens, Victor Gasse, Piotr Mitosek, Robert Raussendorf
Abstract
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.
AI Summary
Given a resource graph state and fixed input/output sets, which assignments of single-qubit measurement planes permit robustly deterministic measurement-based computation? This paper studies this question through gflow, allowing the labels $\{XY,XZ,YZ\}$ to be unspecified or partially constrained, rather than fixed in advance. It gives an $O(n^3)$ algorithm that finds a compatible measurement labelling and witnessing gflow, or determines that none exists, matching the bound for fixed-label gflow finding. The algorithm works backwards from outputs, assigning vertices whose correction stabilisers act only on themselves and already-solved vertices. Three binary linear systems encode the possible measurement planes; incrementally maintained Gaussian elimination shares work across vertices and layers. Per-vertex label restrictions and supplied measurement-order constraints can also be incorporated without changing the asymptotic bound. The returned gflow need not be focused, but a focused one can subsequently be obtained in $O(n^3)$. For balanced open graphs, $|I|=|O|$, the paper proves that at most one measurement-plane labelling admits gflow, using flow-preserving graph transformations. For unbalanced graphs with gflow, it gives an $O(n^3)$ balancing procedure based on focused-set spaces of dimension $|O|-|I|$, adding inputs while changing labels only at newly designated inputs. The results concern gflow, not more general Pauli-flow determinism, and do not characterise all computations supported by a resource state. A randomised variant can reach every valid labelling with positive probability, but exhaustive enumeration may take exponential time and revisit labellings.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 28+6 pages