28 research outputs found
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
No full textGiven a classical query algorithm as a decision tree, when does there exist a
quantum query algorithm with a speed-up over the classical one? We provide a
general construction based on the structure of the underlying decision tree,
and prove that this can give us an up-to-quadratic quantum speed-up. In
particular, we obtain a bounded-error quantum query algorithm of cost
to compute a Boolean function (more generally, a relation) that
can be computed by a classical (even randomized) decision tree of size .
Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a
similar flavor, and gave upper bounds in terms of a quantity which we call the
"guessing complexity" of a decision tree. We identify that the guessing
complexity of a decision tree equals its rank, a notion introduced by
Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory.
This answers a question posed by Lin and Lin, who asked whether the guessing
complexity of a decision tree is related to any complexity-theoretic measure.
We also show a polynomial separation between rank and randomized rank for the
complete binary AND-OR tree.
Beigi and Taghavi constructed span programs and dual adversary solutions for
Boolean functions given classical decision trees computing them and an
assignment of non-negative weights to its edges. We explore the effect of
changing these weights on the resulting span program complexity and objective
value of the dual adversary bound, and capture the best possible weighting
scheme by an optimization program. We exhibit a solution to this program and
argue its optimality from first principles. We also exhibit decision trees for
which our bounds are asymptotically stronger than those of Lin and Lin, and
Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked
whether different weighting schemes could yield better upper bounds
A Framework of Quantum Strong Exponential-Time Hypotheses
No full textThe strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation.
Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in P. As an example, we provide a conditional quantum time lower bound of Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover.
Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds
Quantum Sabotage Complexity
No full textGiven a Boolean function f : {0, 1}n → {0, 1}, the goal in the usual query model is to compute f on an unknown input x ∈ {0, 1}n while minimizing the number of queries to x. One can also consider a "distinguishing"problem denoted by fsab: given an input x ∈ f-1(0) and an input y ∈ f-1(1), either all differing bits are replaced by a ∗, or all differing bits are replaced by †, and an algorithm's goal is to identify which of these is the case while minimizing the number of queries. Ben-David and Kothari [ToC'18] introduced the notion of randomized sabotage complexity of a Boolean function to be the zero-error randomized query complexity of fsab. A natural follow-up question is to understand the Q(fsab), the quantum query complexity of fsab. In this paper, we initiate a systematic study of this. The following are our main results for all Boolean functions f : {0, 1}n → {0, 1}. If we have additional query access to x and y, then Q(fsab) = O(min{Q(f), √n}). If an algorithm is also required to output a differing index of a 0-input and a 1-input, then Q(fsab) = O(min {Q(f)1.5, √n}). Q(fsab) = Ω(√fbs(f)), where fbs(f) denotes the fractional block sensitivity of f. By known results, along with the results in the previous bullets, this implies that Q(fsab) is polynomially related to Q(f). The bound above is easily seen to be tight for standard functions such as And, Or, Majority and Parity. We show that when f is the Indexing function, Q(fsab) = Θ(fbs(f)), ruling out the possibility that Q(fsab) = Θ(√fbs(f)) for all f
Memory Compression with Quantum Random-Access Gates
No full textIn the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may "compress" it into another algorithm which uses only m log M memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree.
We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m log M) memory, and runs in time Õ(T).
We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks
No full textMany computational problems are subject to a quantum speed-up: one might find that a problem having an O(n³)-time or O(n²)-time classic algorithm can be solved by a known O(n^{1.5})-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible?
The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro and Speelman [Buhrman et al., 2021], and by Aaronson, Chia, Lin, Wang, and Zhang [Aaronson et al., 2020].
In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-ε}), for any ε > 0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-ε})-time quantum algorithms for the 3SUM problem.
Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems.
These results are proven by adapting to the quantum setting known classical fine-grained reductions from the 3SUM problem. This adaptation is not trivial, however, since the original classical reductions require pre-processing the input in various ways, e.g. by sorting it according to some order, and this pre-processing (provably) cannot be done in sublinear quantum time.
We overcome this bottleneck by combining a quantum walk with a classical dynamic data-structure having a certain "history-independence" property. This type of construction has been used in the past to prove upper bounds, and here we use it for the first time as part of a reduction. This general proof strategy allows us to prove tight lower bounds on several computational-geometry problems, on Convolution-3SUM and on the 0-Edge-Weight-Triangle problem, conditional on the Quantum-3SUM-Conjecture.
We believe this proof strategy will be useful in proving tight (conditional) lower-bounds, and limits on quantum speed-ups, for many other problems
Fine-Grained Complexity via Quantum Natural Proofs
No full textBuhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be `compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as PARITY and MAJORITY are compression oblivious for certain circuit class if subexponentially secure quantum pseudorandom functions exist in , answering an open question in [Buhrman-Patro-Speelman 2021]
Quantum fine-grained complexity
No full textOne of the major challenges in the field of complexity theory is the inability to prove unconditional time lower bounds, including for practical problems within the complexity class P. One way around this is the study of fine-grained complexity where we use special reductions to prove time-lower bounds for many diverse problems in P based on the conjectured hardness of some key problems. For example, computing the edit distance between two strings, a problem that has a practical interest in the comparing of DNA strings, has an algorithm that takes O(n^2) time. Using a fine-grained reduction it can be shown that faster algorithms for edit distance also imply a faster algorithm for the Boolean Satisfiability (SAT) problem (that is believed to not exist) - strong evidence that it will be very hard to solve the edit distance problem faster. Other than SAT, 3SUM and APSP are other such key problems that are very suitable to use as a basis for such reductions, since they are natural to describe and well-studied. The situation in the quantum regime is no better; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which doesn’t help much for problems for which the best-known algorithms take superlinear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible for various reasons. In this thesis, we present results in which we circumvent these challenges and prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of SAT (and its variants), 3SUM and the APSP problem
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
No full textWhile seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classical counterparts. Moreover, there are problems for which there is no `useful' computational advantage possible with the current quantum hardware. This situation however can be beneficial if we don't want quantum computers to solve certain problems fast - say problems relevant to post-quantum cryptography. In such a situation, we would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity? To do so one has to prove lower bounds, but proving unconditional time lower bounds has never been easy. As a result, resorting to conditional lower bounds has been quite popular in the classical community and is gaining momentum in the quantum community. In this paper, by the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate-#CNFSAT; both of these have interesting implications about the complexity of (variations of) lattice problems, strong simulation and hitting set problem, and more. In the process, we explore the QSETH framework in greater detail than was (required and) discussed in the original paper, thus also serving as a useful guide on how to effectively use the QSETH framework
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
No full textWhile seemingly undesirable, it is not a surprising fact that there are
certain problems for which quantum computers offer no computational advantage
over their respective classical counterparts. Moreover, there are problems for
which there is no `useful' computational advantage possible with the current
quantum hardware. This situation however can be beneficial if we don't want
quantum computers to solve certain problems fast - say problems relevant to
post-quantum cryptography. In such a situation, we would like to have evidence
that it is difficult to solve those problems on quantum computers; but what is
their exact complexity?
To do so one has to prove lower bounds, but proving unconditional time lower
bounds has never been easy. As a result, resorting to conditional lower bounds
has been quite popular in the classical community and is gaining momentum in
the quantum community. In this paper, by the use of the QSETH framework
[Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity
of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT,
and also are able to comment on the non-trivial complexity of
approximate-#CNFSAT; both of these have interesting implications about the
complexity of (variations of) lattice problems, strong simulation and hitting
set problem, and more.
In the process, we explore the QSETH framework in greater detail than was
(required and) discussed in the original paper, thus also serving as a useful
guide on how to effectively use the QSETH framework.Comment: 34 pages, 2 tables, 2 figure
Video for An Overview of Quantum Algorithms: From Quantum Supremacy to Shor Factorization
No full text
