BQP, meet NP: Search-to-decision reductions and approximate counting
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), n.d.
Download
No fulltext has been uploaded.
Conference Paper
| Accepted
| English
Author
Gharibian, SevagLibreCat ;
Kamminga, Jonas
Abstract
What is the power of polynomial-time quantum computation with access to an NP
oracle? In this work, we focus on two fundamental tasks from the study of
Boolean satisfiability (SAT) problems: search-to-decision reductions, and
approximate counting. We first show that, in strong contrast to the classical
setting where a poly-time Turing machine requires $\Theta(n)$ queries to an NP
oracle to compute a witness to a given SAT formula, quantumly $\Theta(\log n)$
queries suffice. We then show this is tight in the black-box model - any
quantum algorithm with "NP-like" query access to a formula requires
$\Omega(\log n)$ queries to extract a solution with constant probability.
Moving to approximate counting of SAT solutions, by exploiting a quantum link
between search-to-decision reductions and approximate counting, we show that
existing classical approximate counting algorithms are likely optimal. First,
we give a lower bound in the "NP-like" black-box query setting: Approximate
counting requires $\Omega(\log n)$ queries, even on a quantum computer. We then
give a "white-box" lower bound (i.e. where the input formula is not hidden in
the oracle) - if there exists a randomized poly-time classical or quantum
algorithm for approximate counting making $o(log n)$ NP queries, then
$\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete
problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$
contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is
quantum.
Publishing Year
Proceedings Title
Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)
LibreCat-ID
Cite this
Gharibian S, Kamminga J. BQP, meet NP: Search-to-decision reductions and approximate counting. In: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).
Gharibian, S., & Kamminga, J. (n.d.). BQP, meet NP: Search-to-decision reductions and approximate counting. Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).
@inproceedings{Gharibian_Kamminga, title={BQP, meet NP: Search-to-decision reductions and approximate counting}, booktitle={Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas} }
Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” In Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), n.d.
S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions and approximate counting.”
Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).