We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.

International audience

This work focuses on understanding the quantum message complexity of two central problems in distributed computing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network topologies.

We show that, for every k ≥ 2, C2k-freeness can be decided in O(n1--1/k) rounds in the CONGEST model by a randomized Monte-Carlo distributed algorithm with one-sided error probability 1/3. This matches the best round-complexities of previously known algorithms for k ∈ {2, 3, 4, 5} by Drucker et al. [PODC'14] and Censor-Hillel et al. [DISC'20], but improves the complexities of the known algorithms for k > 5 by Eden et al. [DISC'19], which were essentially of the form Õ (n1--2/k2). Our algorithm uses colored BFS-explorations with threshold, but with an original global approach that enables to overcome a recent impossibility result by Fraigniaud et al. [SIROCCO'23] about using colored BFS-exploration with local threshold for detecting cycles.

Given x,y ∈ {0,1}ⁿ, Set Disjointness consists in deciding whether x_i = y_i = 1 for some index i ∈ [n]. We study the problem of computing this function in a distributed computing scenario in which the inputs x and y are given to the processors at the two extremities of a path of length d. Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging O(log n) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from 1/2. We call this problem "Set Disjointness on a Line". Set Disjointness on a Line was introduced by Le Gall and Magniez [Le Gall and Magniez, 2018] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of O(log n) qubits. In this work, we prove an unconditional lower bound of Ω̃(∛{n d²} + √n) rounds for Set Disjointness on a Line with d + 1 processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of Ω̃ (∛{nδ²} + √n) on the number of rounds required for computing the diameter δ of any n-node network with quantum messages of size O(log n) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function f (such as Set Disjointness) has access to the inputs x and y through two separate oracles 𝒪_x and 𝒪_y, respectively. The restriction is that the algorithm is required to alternately make d queries to 𝒪_x and d queries to 𝒪_y, with input-independent computation in between queries. The model reflects a "switching delay" of d queries between a "round" of queries to x and the following "round" of queries to y. The technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to this query model. We provide an algorithm for Set Disjointness in this query model with query complexity that matches the round lower bound stated above, up to a polylogarithmic factor. In this sense, the round lower bound we show for Set Disjointness on a Line is optimal.

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC'17), Chang, Pettie and Zhang (SODA'19) and Chang and Saranurak (PODC'19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound O(n) to Õ(n^{1/3}), where n denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in Õ(n^{1/4}) rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now Õ(n^{1/4}) and Θ~(n^{1/3}), respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

In this paper we provide new quantum algorithms with polynomial speed-up for a range of problems for which no such results were known, or we improve previous algorithms. First, we consider the approximation of the frequency moments $F_k$ of order $k \geq 3$ in the multi-pass streaming model with updates (turnstile model). We design a $P$-pass quantum streaming algorithm with memory $M$ satisfying a tradeoff of $P^2 M = \tilde{O}(n^{1-2/k})$, whereas the best classical algorithm requires $P M = Θ(n^{1-2/k})$. Then, we study the problem of estimating the number $m$ of edges and the number $t$ of triangles given query access to an $n$-vertex graph. We describe optimal quantum algorithms that perform $\tilde{O}(\sqrt{n}/m^{1/4})$ and $\tilde{O}(\sqrt{n}/t^{1/6} + m^{3/4}/\sqrt{t})$ queries respectively. This is a quadratic speed-up compared to the classical complexity of these problems. For this purpose we develop a new quantum paradigm that we call Quantum Chebyshev's inequality. Namely we demonstrate that, in a certain model of quantum sampling, one can approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependency is quadratic. Our algorithm subsumes a previous result of Montanaro [Mon15]. This new paradigm is based on a refinement of the Amplitude Estimation algorithm of Brassard et al. [BHMT02] and of previous quantum algorithms for the mean estimation problem. We show that this speed-up is optimal, and we identify another common model of quantum sampling where it cannot be obtained. For our applications, we also adapt the variable-time amplitude amplification technique of Ambainis [Amb10] into a variable-time amplitude estimation algorithm.

In this paper we consider the problem of deciding membership in Dyck languages, a fundamental family of context-free languages, comprised of well-balanced strings of parentheses. In this problem we are given a string of length n in the alphabet of parentheses of m types and must decide if it is well-balanced. We consider this problem in the property testing setting, where one would like to make the decision while querying as few characters of the input as possible. Property testing of strings for Dyck language membership for m = 1, with a number of queries independent of the input size n, was provided in [Alon, Krivelevich, Newman and Szegedy, SICOMP 2001]. Property testing of strings for Dyck language membership for m ≥ 2 was first investigated in [Parnas, Ron and Rubinfeld, RSA 2003]. They showed an upper bound and a lower bound for distinguishing strings belonging to the language from strings that are far (in terms of the Hamming distance) from the language, which are respectively (up to polylogarithmic factors) the 2/3 power and the 1/11 power of the input size n. Here we improve the power of n in both bounds. For the upper bound, we introduce a recursion technique, that together with a refinement of the methods in the original work provides a test for any power of n larger than 2/5. For the lower bound, we introduce a new problem called Truestring Equivalence, which is easily reducible to the 2-type Dyck language property testing problem. For this new problem, we show a lower bound of n to the power of 1/5.

International audience

We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of O(n^(5/4)) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with m >= n^(5/4) edges, we get a query complexity of O(n^(11/12) m^(1/6) sqrt(log n)), which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when m >= n^(3/2). We also obtain an algorithm with query complexity O(n^(5/6) (m log n)^(1/6) + d_2 sqrt(n)) where d_2 is the variance of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall based on the MNRS quantum walk framework [SICOMP'11].

We consider the problem of stable matching with dynamic preference lists. At each time-step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching, in terms of number of blocking pairs, at all time-steps. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly. We design an algorithm that in expectation and with high probability maintains a matching that has at most O((log n)^2 blocking pairs.

In the context of formal language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al., a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs of the language from those that are eps-far from it, while using the smallest possible memory (rather than limiting its number of input queries). Our main result is a streaming eps-property tester for visibly pushdown languages (V_{PL}) with memory space poly(log n /epsilon). Our construction is done in three steps. First, we simulate a visibly pushdown automaton in one pass using a stack of small height but whose items can be of linear size. In a second step, those items are replaced by small sketches. Those sketches rely on a notion of suffix-sampling we introduce. This sampling is the key idea for taking benefit of both streaming algorithms and property testers in the third step. Indeed, the last step relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. This tester can directly be used for streaming testing special cases of instances of V_{PL} that are already hard for both streaming algorithms and property testers. We then use it to decide the correctness of completed items, given their sketches, before removing them from the stack.

We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length n in several of the possible models. In the read-only and write-only model, we show that p-pass algorithms need memory space Theta(n/p). But if either the output stream or the input stream is read-write, then the complexity falls to Theta(n/p^2). It becomes polylog(n) if p = O(log n) and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has O(1) expansion, O(log n) passes and O(log n) memory.

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in $\mathbb{Z}_p^n$, whenever $p$ is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group $G$ is reducible to instances of Translating Coset in $G/N$ and $N$, for appropriate normal subgroups $N$ of $G$. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

Motivated by a concrete problem and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with s different types of parentheses. We present a one-pass randomized streaming algorithm for Dyck(2) with space of ${O}(\sqrt{n\log n}\,)$ bits, time per letter ${polylog}(n)$, and one-sided error. We prove that this one-pass algorithm is optimal, up to a $\log n$ factor, even when two-sided error is allowed. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for Dyck(2) with space of ${O}((\log n)^2)$, time polylog(n) and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to Dyck(s) since this problem is reducible to Dyck(2) for a suitable notion of reduction in the streaming model. Except for an extra ${O}(\sqrt{\log s}\,)$ multiplicative overhead in the space required in the one-pass algorithm, the resource requirements are of the same order. For the lower bound, we exhibit hard instances Ascension(m) of Dyck(2) with length in $\Theta(mn)$. We embed these in what we call a “one-pass” communication problem with 2m-players, where $m \in \tilde{{O}}(n)$. To establish the hardness of Ascension(m), we follow the “information cost” approach, but with a few twists. We prove a direct sum result that reduces Ascension(m) to a two-player protocol for Mountain, which is in fact a variant of Index, a fundamental problem in communication complexity. We finish the argument with a new information cost lower bound for Mountain.

We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the O(n35/27) and O(n9/7) learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|S|3/2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In a context of massive data, one would like to minimize both the amount of reliable memory of the checker and the number of passes on the sequence of operations. Chu, Kannan and McGregor initiated the study of checking priority queues in this setting. They showed that use of timestamps allows to check a priority queue with a single pass and memory space O(N^(1/2)), up to a polylogarithmic factor. Later, Chakrabarti, Cormode, Kondapally and McGregor removed the use of timestamps, and proved that more passes do not help. We show that, even in the presence of timestamps, more passes do not help, solving a previously open problem. On the other hand, we show that a second pass, but in reverse direction, shrinks the memory space to O((log N)^2), extending a phenomenon the first time observed by Magniez, Mathieu and Nayak for checking well-parenthesized expressions.

We study the problem of validating XML documents of size N against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which p -pass streaming algorithms require Ω( N / p ) space. We show that when allowing access to external memory, there is a deterministic streaming algorithm that solves this problem with memory space O(log 2 N ), a constant number of auxiliary read/write streams, and O(log N ) total number of passes on the XML document and auxiliary streams. An important intermediate step of this algorithm is the computation of the First-Child-Next-Sibling (FCNS) encoding of the initial XML document in a streaming fashion. We study this problem independently, and we also provide memory-efficient streaming algorithms for decoding an XML document given in its FCNS encoding. Furthermore, validating XML documents encoding binary trees against any DTD in the usual streaming model without external memory can be done with sublinear memory. There is a one-pass algorithm using O(√ N log N ) space, and a bidirectional two-pass algorithm using O(log 2 N ) space which perform this task.

We study the problem of validating XML documents of size N against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which p-pass streaming algorithms require Ω(N/p) space.

The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find —a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem (Tulsi A.: Phys. Rev. A 78 :012310 2008 ) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. Further, we prove that for any reversible ergodic Markov chain P , the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P . We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.

We propose a new method for designing quantum search algorithms for finding a “marked” element in the state space of a classical Markov chain. The algorithm is based on a quantum walk à la Szegedy [Quantum speed-up of Markov chain based algorithms, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 32–41] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis [Quantum walk algorithm for Element Distinctness, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 22–31] and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.

Motivated by a concrete problem and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with s different types of parenthesis.

Inspired by property testing, for every $\varepsilon>0$ we relax the classical satisfiability $U\models F$ between a finite structure U of a class $\mathbf{K}$ and a formula F, to a notion of $\varepsilon$-satisfiability $U\models_{\varepsilon}F$, and relax the classical equivalence $F_1\equiv F_2$ between two formulas $F_1$ and $F_2$ to $\varepsilon$-equivalence $F_1\equiv_{\varepsilon}F_2$. We consider strings and trees with the norm of the edit distance with moves, and show that, unlike their exact counterparts, these approximate notions can be efficiently decided. We use a statistical embedding of words (resp., trees) into $\ell_1$, which generalizes the original Parikh mapping, obtained by sampling $O(f(\varepsilon))$ finite samples of the words (resp., trees). We give a tester for equality and membership in any regular language, in time independent of the size of the structure. Using our geometrical embedding, we can also test the equivalence between two regular properties over words, defined by regular expressions or monadic second-order formulas. Our equivalence tester has polynomial time complexity in the size of the automaton (or regular expression), for any fixed $\varepsilon$, whereas the exact version of the equivalence problem is PSPACE-complete. We also prove versions of some of these results for trees, but with worse time complexity. Last, we extend the geometric embedding, and hence the testing algorithms, to infinite regular languages and to context-free languages. For context-free languages, the equivalence tester has an exponential time complexity for any fixed $\varepsilon$, whereas the exact version is not even decidable.

We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.

We prove a very general lower bound technique for quantum and randomized query complexity that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted and unweighted methods of Ambainis and the spectral method of Barnum, Saks, and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in $O(\min(\sqrt{n C_0(f)},\sqrt{n C_1(f)}))$, where $C_0, C_1$ is the certificate complexity and n is the size of the input.

We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.

We consider the design of self-testers for quantum gates. A self-tester for the gates $\boldsymbol{F}_1,\ldots, \boldsymbol{F}_m$ is a procedure that, given any gates $\boldsymbol{G}_1, \ldots, \boldsymbol{G}_m$, decides with high probability if each $\boldsymbol{G}_i$ is close to $\boldsymbol{F}_i$. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that, instead of individual gates, we can design only procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: We characterize the gate families by specific properties, develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a $\mathrm{c\text{-}NOT}$ gate, and a phase rotation gate of angle $\pi/4$ is self-testable.

We present two new quantum algorithms that either find a triangle (a copy of $K_{3}$) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes $\tilde{O}(n^{10/7})$ queries. The second algorithm uses $\tilde{O}(n^{13/10})$ queries and is based on a design concept of Ambainis [in Proceedings of the $45$th IEEE Symposium on Foundations of Computer Science, 2004, pp. 22–31] that incorporates the benefits of quantum walks into Grover Search [L. Grover, in Proceedings of the Twenty‐Eighth ACM Symposium on Theory of Computing, 1996, pp. 212–219]. The first algorithm uses only $O(\log n)$ qubits in its quantum subroutines, whereas the second one uses $O(n)$ qubits. The Triangle Problem was first treated in [H. Buhrman et al., SIAM J. Comput., 34 (2005), pp. 1324–1330], where an algorithm with $O(n+\sqrt{nm})$ query complexity was presented, where m is the number of edges of G.

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions. Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, “sufficiently” incorrect programs will be rejected (ε-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness). Our work applies to programs for graph properties such as bipartiteness, k -colorability, or any ∃∀ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.

Inspired by property testing, we relax the classical satisfiability UvDashF between a finite structure U of a class K and a formula F, to a notion of epsiv-satisfiability UvDashepsivF, and the classical equivalence F1equivF2between two formulas F1and F2, to epsiv-equivalence F1equivepsivF2for epsiv>0. We consider the class of strings and trees with the edit distance with moves, and show that these approximate notions can be efficiently decided. We use a statistical embedding of words (resp. trees) into lscr1, which generalizes the original Parikh mapping, obtained by sampling O(f(epsiv)) finite samples of the words (resp. trees). We give a tester for equality and membership in any regular language, in time independent of the size of the structure. Using our geometrical embedding, we can also test the equivalence between two regular properties on words, defined by monadic second order formulas. Our equivalence tester has polynomial time complexity in the size of the automaton (or regular expression), for a fixed epsiv, whereas the exact version of the equivalence problem is PSPACE-complete. Last, we extend the geometric embedding, and hence the tester algorithms, to infinite regular languages and to context-free languages. For context-free languages, the equivalence tester has an exponential time complexity, whereas the exact version is undecidable

We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables, and for finding a triangle in a graph. Our techniques generalize and improve those of Brassard, Hoyer, and Tapp [ACM SIGACT News, 28 (1997), pp. 14--19]. This shows that in the quantum world element distinctness is significantly easier than sorting, in contrast to the classical world.

We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for Boolean functions f in 0(min((/spl radic/nC/sup 0/(f)), (/spl radic/nC/sup 0/(f)))) where C/sup 0/, C/sup 1/ is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Hoyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z pn, whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup, and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N, for any solvable normal subgroup N of G.

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions. Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, "sufficiently" incorrect programs will be rejected (E-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness). Our work applies to programs for graph properties such as bipartiteness, k-colorability, or any /spl exist//spl forall/ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.

We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp (1998), and imply an O(N/sup 3/4/ log N) quantum upper bound for the element distinctness problem in the comparison complexity model. This contrasts with /spl Theta/(N log N) classical complexity. We also prove a lower bound of /spl Omega/(/spl radic/N) comparisons for this problem and derive bounds for a number of related problems.

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

Abstract. We consider the design of self-testers for quantum gates. A self-tester for the gates F 1,..., F m is a procedure that, given any gates G1,..., Gm, decides with high probability if each Gi is close to F i. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that instead of individual gates, we can only design procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: we characterize the gate families by specific properties, we develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT gate, and a phase rotation gate of angle π/4 is self-testable. 1. Introduction. In

We formalize the notion and initiate the investigation of approximate testing for arbitrary forms of the error term. Until now only the case of absolute error had been addressed ignoring the fact that often only the most significant figures of a numerical calculation are valid. This work considers approximation errors whose magnitude grows with the size of the input to the program. We demonstrate the viability of this new concept by addressing the basic and benchmark problem of self-- testing for the class of linear and polynomial functions. We obtain stronger versions of results of Ergun, Ravi Kumar, and Rubinfeld [EKR96] by exploiting elegant techniques from Hyers--Ulam stability theory. 1 Introduction The following is a quote from Knuth [Knu98, Ch. 4, x 2.2]: Floating point computation is by nature inexact, and programmers can easily misuse it so that the computed answers consist almost entirely of "noise." One of the principal problems of numerical analysis is to determine how ac...