Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an
Quantum algorithms and lower bounds for convex optimization
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the bestknown classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.
more »
« less
 Award ID(s):
 1816695
 NSFPAR ID:
 10106373
 Date Published:
 Journal Name:
 Quantum
 Volume:
 4
 ISSN:
 2521327X
 Page Range / eLocation ID:
 221
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

n dimensional convex body within multiplicative error ε usingÕ(n^{3}+ n^{2.5}/ε ) queries to a membership oracle andÕ(n^{5}+n^{4.5}/ε) additional arithmetic operations. For comparison, the best known classical algorithm usesÕ(n^{3.5}+n^{3}/ε^{2}) queries andÕ(n^{5.5}+n^{5}/ε^{2}) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuousspace quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requiresΩ (√ n+1/ε) quantum membership queries, which rules out the possibility of exponential quantum speedup inn and shows optimality of our algorithm in 1/ε up to polylogarithmic factors. 
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an ndimensional convex body within multiplicative error ϵ using Õ (n3+n2.5/ϵ) queries to a membership oracle and Õ (n5+n4.5/ϵ) additional arithmetic operations. For comparison, the best known classical algorithm uses Õ (n4+n3/ϵ2) queries and Õ (n6+n5/ϵ2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuousspace quantum walks with rigorous bounds on discretization error.more » « less

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottomlevel gates. Let f be an m bit Boolean function and consider an n bit function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ) , we give an algorithm for evaluating F using O ~ ( Q ( f ) ⋅ n ) quantum queries. This improves on the bound of O ( Q ( f ) ⋅ n ) that follows by treating each conjunction independently, and our bound is tight for worstcase choices of f . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f .By recursively applying our composition theorems, we obtain a nearly optimal O ~ ( n 1 − 2 − d ) upper bound on the quantum query complexity and approximate degree of linearsize depth d AC 0 circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponentialtime algorithm was not known even for linearsize depth3 AC 0 circuits.As an additional consequence, we show that AC 0 ∘ ⊕ circuits of depth d + 1 require size Ω ~ ( n 1 / ( 1 − 2 − d ) ) ≥ ω ( n 1 + 2 − d ) to compute the Inner Product function even on average. The previous best size lower bound was Ω ( n 1 + 4 − ( d + 1 ) ) and only held in the worst case (Cheraghchi et al., JCSS 2018).more » « less

Cumulative memory – the sum of space used per step over the duration of a computation – is a finegrained measure of timespace complexity that was introduced to analyze cryptographic applications like password hashing. It is a more accurate cost measure for algorithms that have infrequent spikes in memory usage and are run in environments such as cloud computing that allow dynamic allocation and deallocation of resources during execution, or when many multiple instances of an algorithm are interleaved in parallel. We prove the first lower bounds on cumulative memory complexity for both sequential classical computation and quantum circuits. Moreover, we develop general paradigms for bounding cumulative memory complexity inspired by the standard paradigms for proving timespace tradeoff lower bounds that can only lower bound the maximum space used during an execution. The resulting lower bounds on cumulative memory that we obtain are just as strong as the best timespace tradeoff lower bounds, which are very often known to be tight. Although previous results for pebbling and random oracle models have yielded timespace tradeoff lower bounds larger than the cumulative memory complexity, our results show that in general computational models such separations cannot follow from known lower bound techniques and are not true for many functions. Among many possible applications of our general methods, we show that any classical sorting algorithm with success probability at least 1/poly(n) requires cumulative memory Ω(n^2), any classical matrix multiplication algorithm requires cumulative memory Ω(n^6/T), any quantum sorting circuit requires cumulative memory Ω(n^3/T), and any quantum circuit that finds k disjoint collisions in a random function requires cumulative memory Ω(k^3 n/T^2). (Full version of ICALP 2023 paper.)more » « less

Cumulative memory – the sum of space used per step over the duration of a computation – is a finegrained measure of timespace complexity that was introduced to analyze cryptographic applications like password hashing. It is a more accurate cost measure for algorithms that have infrequent spikes in memory usage and are run in environments such as cloud computing that allow dynamic allocation and deallocation of resources during execution, or when many multiple instances of an algorithm are interleaved in parallel. We prove the first lower bounds on cumulative memory complexity for both sequential classical computation and quantum circuits. Moreover, we develop general paradigms for bounding cumulative memory complexity inspired by the standard paradigms for proving timespace tradeoff lower bounds that can only lower bound the maximum space used during an execution. The resulting lower bounds on cumulative memory that we obtain are just as strong as the best timespace tradeoff lower bounds, which are very often known to be tight. Although previous results for pebbling and random oracle models have yielded timespace tradeoff lower bounds larger than the cumulative memory complexity, our results show that in general computational models such separations cannot follow from known lower bound techniques and are not true for many functions. Among many possible applications of our general methods, we show that any classical sorting algorithm with success probability at least 1/poly(n) requires cumulative memory Ω(n^2), any classical matrix multiplication algorithm requires cumulative memory Ω(n^6/T), any quantum sorting circuit requires cumulative memory Ω(n^3/T), and any quantum circuit that finds k disjoint collisions in a random function requires cumulative memory Ω(k^3 n/T^2).more » « less