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), 2024, pp. 1–19.

Download
No fulltext has been uploaded.
Conference Paper | Published | 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)
Volume
297
Issue
70
Page
1-19
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). Vol 297. ; 2024:1-19.
Gharibian, S., & Kamminga, J. (2024). BQP, meet NP: Search-to-decision reductions and approximate counting. Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 297(70), 1–19.
@inproceedings{Gharibian_Kamminga_2024, title={BQP, meet NP: Search-to-decision reductions and approximate counting}, volume={297}, number={70}, booktitle={Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2024}, pages={1–19} }
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), 297:1–19, 2024.
S. Gharibian and J. Kamminga, “BQP, meet NP: Search-to-decision reductions and approximate counting,” in Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, vol. 297, no. 70, pp. 1–19.
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), vol. 297, no. 70, 2024, pp. 1–19.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 2401.03943

Search this title in

Google Scholar