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

arXiv:quant-ph/0603072

A complete algorithm to find flows in the one-way measurement model

Niel de Beaudrap

Published Mar 8, 2006• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0603072

Related papers

Finding flows in the one-way measurement model

Niel de Beaudrap

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 $\mathit{I}$, $\mathit{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.

arXiv:quant-ph/0611284•Physical Review A•Feb 29, 2008•35 citations

An extremal result for geometries in the one-way measurement model

Niel de Beaudrap, Martin Pei

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 \subseteq 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 $\lvert I \rvert = \lvert O \rvert = k$ (corresponding to unitary transformations in the measurement model) and $\lvert V(G) \rvert = n$ can be performed in time $O(k^2 n)$, improving the earlier known bound of $O(km)$ given in \cite{B06a}, where $m = \lvert E(G) \rvert$.

arXiv:quant-ph/0702229•Quantum Information and Computation•May 1, 2008•9 citations

Comments on quant-ph/0609176

Wu, XiaoDi

In this note, we show the mistake which has been made in quant-ph/0609176. Further more, we provide a sketch of proof to show the impossibility of the effort of such kind toward improving the efficiency of Grover's Algorithm.

arXiv:quant-ph/0701035•Jan 8, 2007•0 citations

Optimising the information flow of one-way quantum computations

Einar Pius, Raphael Dias da Silva, Elham Kashefi

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.

Quantum Information and Computation•Jul 1, 2015•1 citation

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

Yota Maeda, Hiroshi Yano

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \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 $\log q$. 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.

quant-pharXiv:2608.23929•Aug 26, 2026•0 citations

A minimization algorithm of 1-way quantum finite automata

Olga Siedlecka-Lamch

Metody Informatyki Stosowanej•Jan 1, 2010•0 citations
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 GGG 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 GGG, together with input and output I\mathit{I}I, O\mathit{O}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∣|I|=|O|∣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 GGG which (together with some specified sets of input and output vertices, III and OOO) 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)(G,I,O)(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 GGG may have, in order for a triple (G,I,O)(G,I,O)(G,I,O) to have a flow for some I,O⊆V(G)I, O \subseteq V(G)I,O⊆V(G), in terms of the number of vertices in GGG and OOO. This implies that finding a flow for a triple (G,I,O)(G,I,O)(G,I,O) when ∣I∣=∣O∣=k\lvert I \rvert = \lvert O \rvert = k∣I∣=∣O∣=k (corresponding to unitary transformations in the measurement model) and ∣V(G)∣=n\lvert V(G) \rvert = n∣V(G)∣=n can be performed in time O(k2n)O(k^2 n)O(k2n), improving the earlier known bound of O(km)O(km)O(km) given in \cite{B06a}, where m=∣E(G)∣m = \lvert E(G) \rvertm=∣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)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.
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],f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], f(x)=∑j=1s​aj​xuj​∈Fq​[x1±1​,…,xn±1​], let UUU be its augmented support matrix whose columns are (1,uj)(1,u_j)(1,uj​) with rank ρρρ and N(f):=#{x∈(Fq×)n∣f(x)=0}N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}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)\widehat{N}(f)N(f) satisfying ∣N^(f)−N(f)∣≤εqn+s/2−ρ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} ∣N(f)−N(f)∣≤εqn+s/2−ρ with success probability 1−δ1-δ1−δ. Provided that ρρρ and ∥U∥∞\|U\|_\infty∥U∥∞​ are bounded, the algorithm runs in both classical bit and quantum gate complexity poly(n,s,log⁡q,1/ε,log⁡(1/δ))\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))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 log⁡q\log qlogq. 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 UUU 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.