BQP, meet NP: Search-to-decision reductions and approximate counting

Sevag Gharibian, Jonas Kamminga

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)…