Source author record

Aleksandrs Belovs

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Computational Complexity Data Structures and Algorithms Cryptography and Security Discrete Mathematics Emerging Technologies Formal Languages and Automata Theory

Catalog footprint

Research overview

22works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

One-Way Ticket to Las Vegas and the Quantum Adversary

We propose a new definition of quantum Las Vegas query complexity. We show that it is exactly equal to the quantum adversary bound. This is achieved by a new and very simple way of transforming a feasible solution to the adversary optimisation problem into a quantum query algorithm. This allows us to generalise the bound to include unidirectional access, multiple input oracles, and input oracles that are not unitary. As an application, we demonstrate a separation between unidirectional and bidirectional access to an input oracle for a rather natural unitary permutation inversion problem.

preprint2020arXiv

Quantum Coupon Collector

We study how efficiently a $k$ -element set $S\subseteq[n]$ can be learned from a uniform superposition $|S\rangle$ of its elements. One can think of $|S\rangle=\sum_{i\in S}|i\rangle/\sqrt{|S|}$ as the quantum version of a uniformly random sample over $S$ , as in the classical analysis of the ``coupon collector problem.'' We show that if $k$ is close to $n$ , then we can learn $S$ using asymptotically fewer quantum samples than random samples. In particular, if there are $n-k=O(1)$ missing elements then $O(k)$ copies of $|S\rangle$ suffice, in contrast to the $Θ(k\log k)$ random samples needed by a classical coupon collector. On the other hand, if $n-k=Ω(k)$ , then $Ω(k\log k)$ quantum samples are~necessary. More generally, we give tight bounds on the number of quantum samples needed for every $k$ and $n$ , and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through $|S\rangle$ . Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.

preprint2020arXiv

The quantum query complexity of composition with a relation

The negative weight adversary method, $\mathrm{ADV}^\pm(g)$ , is known to characterize the bounded-error quantum query complexity of any Boolean function $g$ , and also obeys a perfect composition theorem $\mathrm{ADV}^\pm(f \circ g^n) = \mathrm{ADV}^\pm(f) \mathrm{ADV}^\pm(g)$ . Belovs gave a modified version of the negative weight adversary method, $\mathrm{ADV}_{rel}^\pm(f)$ , that characterizes the bounded-error quantum query complexity of a relation $f \subseteq \{0,1\}^n \times [K]$ , provided the relation is efficiently verifiable. A relation is efficiently verifiable if $\mathrm{ADV}^\pm(f_a) = o(\mathrm{ADV}_{rel}^\pm(f))$ for every $a \in [K]$ , where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) \in f$ . In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ $\mathrm{ADV}_{rel}^\pm(f \circ g^n) = \mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) \enspace .$ For an efficiently verifiable relation $f$ this means $Q(f \circ g^n) = Θ( \mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) )$ .

preprint2016arXiv

Can one quantum bit separate any pair of words with zero-error?

Determining the minimum number of states required by a finite automaton to separate a given pair of different words is an important problem. In this paper, we consider this problem for quantum automata (QFAs). We show that 2-state QFAs can separate any pair of words in nondeterministic acceptance mode and conjecture that they can separate any pair also with zero-error. Then, we focus on (a more general problem) separating a pair of two disjoint finite set of words. We show that QFAs can separate them efficiently in nondeterministic acceptance mode, i.e. the number of states is two to the power of the size of the small set. Additionally, we examine affine finite automata (AfAs) and show that two states are enough to separate any pair with zero-error. Moreover, AfAs can separate any pair of disjoint finite sets of words with one-sided bounded error efficiently like QFAs in nondeterministic mode.

preprint2016arXiv

Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness

We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$ -vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.

preprint2015arXiv

A Polynomial Lower Bound for Testing Monotonicity

We show that every algorithm for testing $n$ -variate Boolean functions for monotonicity must have query complexity $\tildeΩ(n^{1/4})$ . All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only $Ω(\log n)$ . Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that non-adaptive algorithms require almost $Ω(n^{1/2})$ queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity $O(\log n)$ when the input is a regular LTF.

preprint2015arXiv

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

In the $k$ -junta testing problem, a tester has to efficiently decide whether a given function $f:\{0,1\}^n\rightarrow \{0,1\}$ is a $k$ -junta (i.e., depends on at most $k$ of its input bits) or is $ε$ -far from any $k$ -junta. Our main result is a quantum algorithm for this problem with query complexity $\tilde O(\sqrt{k/ε})$ and time complexity $\tilde O(n\sqrt{k/ε})$ . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of $Ω(k^{1/3})$ queries for junta-testing (for constant $ε$ ).

preprint2015arXiv

Quantum Algorithm for Monotonicity Testing on the Hypercube

In this note, we develop a bounded-error quantum algorithm that makes $\tilde O(n^{1/4}\varepsilon^{-1/2})$ queries to a Boolean function $f$ , accepts a monotone function, and rejects a function that is $\varepsilon$ -far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all $\varepsilon = o(1)$ . The improvement is cubic when $\varepsilon = 1/\sqrt{n}$ .

preprint2015arXiv

Quantum lower bound for inverting a permutation with advice

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$ , we want to output $x = f^{-1}(y)$ . Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$ . Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$ , can invert $f$ in time $\tilde{O}(T)$ , for every choice of parameters $S$ , $T$ , such that $S\cdot T \ge N$ . We prove a quantum lower bound of $T^2\cdot S \ge \tildeΩ(εN)$ for quantum algorithms that invert a random permutation $f$ on an $ε$ fraction of inputs, where $T$ is the number of queries to $f$ and $S$ is the amount of advice. This answers an open question of De et al. We also give a $Ω(\sqrt{N/m})$ quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit $x_j$ , given the ability to query an $N$ -bit string $x$ at any index except the $j$ -th, and also given $m$ bits of advice that depend on $x$ but not on $j$ .

preprint2015arXiv

Separations in Query Complexity Based on Pointer Functions

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$ , which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$ . We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $Ω(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$ . We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$ , giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total boolean function $g$ on $n$ variables that has zero-error randomized query complexity $Ω(n/\log(n))$ and bounded-error randomized query complexity $R(g) = \tilde O(\sqrt{n})$ . This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is $Q_E(g) = \tilde O(\sqrt{n})$ . These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f) = \tilde O(R(f)^2)$ are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between $Q$ and $R_0$ , a $3/2$ -power separation between $Q_E$ and $R$ , and a 4th power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by \goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

preprint2015arXiv

Variations on Quantum Adversary

The (negative-weighted) quantum adversary bound is a tight characterisation of the quantum query complexity for any partial function. We analyse the extent to which this bound can be generalised. Ambainis et al. [arXiv:1012.2112] and Lee et al. [arXiv:1011.3020] generalised this bound to the state generation and state conversion problems, respectively. Using the ideas by Lee et al., we get even further generalisations of the bound. We obtain a version of the bound for general input oracles, which are just arbitrary unitaries. We also generalise the bound to the problem of implementing arbitrary unitary transformations. Similarly to the bound by Lee et al., our bound is a lower bound for exact transformation and an upper bound for approximate transformation. This version of the bound possesses the tight composition property. Using this construction, we also obtain lower bounds on the quantum query complexity of functions and relations with general input oracles.

preprint2014arXiv

Applications of the Adversary Method in Quantum Query Algorithms

In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the $k$ -distinctness problems. * We prove tight lower bounds for the $k$ -sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.

preprint2014arXiv

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function $f$ on $n$ variables that only depends on $k$ variables, and, when restricted to them, equals some predefined function $h$ . The task is to identify the variables the function depends on. When $h$ is the XOR or the OR function, this gives a restricted variant of the Bernstein-Vazirani or the combinatorial group testing problem, respectively. We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when $h$ is the OR function (complexity is $Θ(\sqrt{k})$ ) or the exact-half function (complexity is $Θ(k^{1/4})$ ). The first algorithm resolves an open problem from arXiv:1210.1148. For the case when $h$ is the majority function, we prove an upper bound of $O(k^{1/4})$ . All these algorithms can be made exact. We obtain a quartic improvement when compared to the randomised complexity (if $h$ is the exact-half or the majority function), and a quadratic one when compared to the non-adaptive quantum complexity (for all functions considered in the paper).

preprint2013arXiv

Quantum Walks and Electric Networks

We prove that a quantum walk can detect the presence of a marked element in a graph in $O(\sqrt{WR})$ steps for any initial probability distribution on vertices. Here, $W$ is the total weight of the graph, and $R$ is the effective resistance. This generalizes the result by Szegedy that is only applicable if the initial distribution is stationary. We describe a time-efficient quantum algorithm for 3-distinctness based on these ideas.

preprint2012arXiv

Adversary Lower Bound for Element Distinctness

In this note we construct an explicit optimal (negative-weight) adversary matrix for the element distinctness problem, given that the size of the alphabet is sufficiently large.

preprint2012arXiv

Adversary Lower Bound for the k-sum Problem

We prove a tight quantum query lower bound $Ω(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.

preprint2012arXiv

Learning-Graph-Based Quantum Algorithm for k-distinctness

We present a quantum algorithm solving the $k$ -distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$ -query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}α^{1/6})$ algorithm for the graph collision problem where $α$ is the independence number of the graph.

preprint2012arXiv

On the Power of Non-Adaptive Learning Graphs

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays, and generalizes the quantum query lower bound for the $k$ -sum problem derived recently in arXiv:1206.6528. Finally, we use these results to show that the learning graph for the triangle problem from arXiv:1210.1014 is almost optimal in these settings. This also gives a quantum query lower bound for the triangle-sum problem.

preprint2012arXiv

Span programs and quantum algorithms for st-connectivity and claw detection

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T as a minor, we give O(n)-query quantum algorithms for detecting T either a triangle or a subdivision of a star. All these algorithms can be implemented time efficiently and, except for the triangle-detection algorithm, in logarithmic space. One of the main techniques is to modify the st-connectivity span program to drop along the way "breadcrumbs," which must be retrieved before the path from s is allowed to enter t.

preprint2011arXiv

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input

It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for $k$ -distinctness problem that runs in $o(n^{3/4})$ queries, for a fixed $k$ , given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$ queries.

preprint2011arXiv

Span Programs for Functions with Constant-Sized 1-certificates

Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity $O(n^{35/27})$ that is better than $O(n^{13/10})$ of the best previously known algorithm by Magniez et al.

preprint2011arXiv

Span-program-based quantum algorithm for the rank problem

Recently, span programs have been shown to be equivalent to quantum query algorithms. It is an open problem whether this equivalence can be utilized in order to come up with new quantum algorithms. We address this problem by providing span programs for some linear algebra problems. We develop a notion of a high level span program, that abstracts from loading input vectors into a span program. Then we give a high level span program for the rank problem. The last section of the paper deals with reducing a high level span program to an ordinary span program that can be solved using known quantum query algorithms.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Aleksandrs Belovs

Research overview

Is this your work?

22 publications

One-Way Ticket to Las Vegas and the Quantum Adversary

Quantum Coupon Collector

The quantum query complexity of composition with a relation

Can one quantum bit separate any pair of words with zero-error?

Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness

A Polynomial Lower Bound for Testing Monotonicity

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Quantum Algorithm for Monotonicity Testing on the Hypercube

Quantum lower bound for inverting a permutation with advice

Separations in Query Complexity Based on Pointer Functions

Variations on Quantum Adversary

Applications of the Adversary Method in Quantum Query Algorithms

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

Quantum Walks and Electric Networks

Adversary Lower Bound for Element Distinctness

Adversary Lower Bound for the k-sum Problem

Learning-Graph-Based Quantum Algorithm for k-distinctness

On the Power of Non-Adaptive Learning Graphs

Span programs and quantum algorithms for st-connectivity and claw detection

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input

Span Programs for Functions with Constant-Sized 1-certificates

Span-program-based quantum algorithm for the rank problem

See the researcher in context

Building this map preview