This article is the complement to [quant-ph/0611284], which proves that flows (as introduced by [quant-ph/0506062]) can be found efficiently for patterns in the one-way measurement model which have non-empty input and output subsystems of the same size. This article presents a complete algorithm for finding flows, and a proof of its' correctness, without assuming any knowledge of graph-theoretic algorithms on the part of the reader. This article is a revised version of [quant-ph/0603072v2], where the results of [quant-ph/0611284] also first appeared.
This article is the complement to [quant-ph/0611284], which proves that flows (as introduced by [quant-ph/0506062]) can be found efficiently for patterns in the one-way measurement model which have non-empty input and output subsystems of the same size. This article presents a complete algorithm for finding flows, and a proof of its' correctness, without assuming any knowledge of graph-theoretic algorithms on the part of the reader. This article is a revised version of [quant-ph/0603072v2], where the results of [quant-ph/0611284] also first appeared.
The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph G of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph G, together with input and output I, O vertices $I,O\ensuremath{\subseteq}V(G)$, to have a flow in the sense introduced by Danos and Kashefi [Phys. Rev. A 74, 052310 (2006)]. For the special case of ∣I∣=∣O∣, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.
We present an extremal result for the class of graphs G which (together with some specified sets of input and output vertices, I and O) have a certain ``flow'' property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple (G,I,O) allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph G may have, in order for a triple (G,I,O) to have a flow for some I,O⊆V(G), in terms of the number of vertices in G and O. This implies that finding a flow for a triple (G,I,O) when ∣I∣=∣O∣=k (corresponding to unitary transformations in the measurement model) and ∣V(G)∣=n can be performed in time O(k2n), improving the earlier known bound of O(km) given in \cite{B06a}, where m=∣E(G)∣.
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.
We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial f(x)=∑j=1sajxuj∈Fq[x1±1,…,xn±1], let U be its augmented support matrix whose columns are (1,uj) with rank ρ and N(f):=#{x∈(Fq×)n∣f(x)=0} be its torus point count. Our first main result is a quantum algorithm that outputs N(f) satisfying ∣N(f)−N(f)∣≤εqn+s/2−ρ with success probability 1−δ. Provided that ρ and ∥U∥∞ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,logq,1/ε,log(1/δ)). It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in logq. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes #P-hard under randomized polynomial-time Turing reductions when the support matrix U varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.