License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.7
URN: urn:nbn:de:0030-drops-125593
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12559/
Aaronson, Scott ;
Kothari, Robin ;
Kretschmer, William ;
Thaler, Justin
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Abstract
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents). Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set S ⊆ [N], in two natural generalizations of quantum query complexity.
Our first result holds in the standard Quantum Merlin - Arthur (QMA) setting, in which a quantum algorithm receives an untrusted quantum witness. We show that, if the algorithm makes T quantum queries to S, and also receives an (untrusted) m-qubit quantum witness, then either m = Ω(|S|) or T = Ω(√{N/|S|}). This is optimal, matching the straightforward protocols where the witness is either empty, or specifies all the elements of S. As a corollary, this resolves the open problem of giving an oracle separation between SBP, the complexity class that captures approximate counting, and QMA.
In our second result, we ask what if, in addition to a membership oracle for S, a quantum algorithm is also given "QSamples" - i.e., copies of the state |S⟩ = 1/√|S| ∑_{i ∈ S} |i⟩ - or even access to a unitary transformation that enables QSampling? We show that, even then, the algorithm needs either Θ(√{N/|S|}) queries or else Θ(min{|S|^{1/3},√{N/|S|}}) QSamples or accesses to the unitary.
Our lower bounds in both settings make essential use of Laurent polynomials, but in different ways.
BibTeX - Entry
@InProceedings{aaronson_et_al:LIPIcs:2020:12559,
author = {Scott Aaronson and Robin Kothari and William Kretschmer and Justin Thaler},
title = {{Quantum Lower Bounds for Approximate Counting via Laurent Polynomials}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {7:1--7:47},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-156-6},
ISSN = {1868-8969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12559},
URN = {urn:nbn:de:0030-drops-125593},
doi = {10.4230/LIPIcs.CCC.2020.7},
annote = {Keywords: Approximate counting, Laurent polynomials, QSampling, query complexity}
}
|
Keywords: |
|
Approximate counting, Laurent polynomials, QSampling, query complexity |
|
Collection: |
|
35th Computational Complexity Conference (CCC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
17.07.2020 |
