Quantum speedups need structure

Publication date 9 November 2019

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Boolean functions (06E30)

Abstract: We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let

f : {- 1, 1}^{n} i g h t a r r o w [- 1, 1]

be a multilinear polynomial of degree

d

. Then there exists a variable

x_{i}

whose influence on

f

is at least

m a t h r m p o l y (m a t h r m V a r (f) / d)

. As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let

Q

be a quantum algorithm that makes

T

queries to a Boolean input and let

e p s i l o n, d e l t a > 0

. Then there exists a deterministic classical algorithm that makes

m a t h r m p o l y (T, 1 / e p s i l o n, 1 / d e l t a)

queries to the input and that approximates

Q

's acceptance probability to within an additive error

e p s i l o n

on a

1 - d e l t a

fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.

This page was built for publication: Quantum speedups need structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328850)