تقرير
BQP, meet NP: Search-to-decision reductions and approximate counting
| العنوان: | BQP, meet NP: Search-to-decision reductions and approximate counting |
|---|---|
| المؤلفون: | Gharibian, Sevag, Kamminga, Jonas |
| المصدر: | 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Volume 297, pp. 70:1-70:19 |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Computational Complexity |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4230/LIPIcs.ICALP.2024.70 |
| URL الوصول: | http://arxiv.org/abs/2401.03943 |
| رقم الأكسشن: | edsarx.2401.03943 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4230/LIPIcs.ICALP.2024.70 |
|---|