Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > QUANTUM QUERY ALGORITHMS:
Reports tagged with quantum query algorithms:
TR24-035 | 20th February 2024
Sreejata Bhattacharya

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Revisions: 1

In an attempt to show that the acceptance probability of a quantum query algorithm making q queries can be well-approximated almost everywhere by a classical decision tree of depth \leq \text{poly}(q), Aaronson and Ambainis proposed the following conjecture: let f: \{ \pm 1\}^n \rightarrow [0,1] be a degree d polynomial ... more >>>




ISSN 1433-8092 | Imprint