Skip to content
DraconiticResearch
Search Sources API
182,460 studies31 sourcesUpdated 47 min ago
PreprintCC BY 4.0arXiv

State Synthesis with an NP oracle

  • Aniruddha Sen
Open at sourcePDFDOICite

Abstract

In this note, I describe a quantum algorithm that prepares an arbitrary state |ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP oracle, assuming one can directly query entries of the state vector corresponding to |ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP. I provide evidence that NP is the best possible upper bound by showing that any quantum algorithm using a P oracle, or even a P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA search-to-decision problem and unitary synthesis.

Related

  1. Magic in Grover's Algorithm and the Role of Oracle Synthesis
    Alessio Paviglianiti, Vincenzo Savona
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Random-Oracle Unitary Synthesis is Impossible
    Andrew Huang, Akshar Ramkumar, John Wright
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Oracle Synthesis Based on X-Map Decision Diagrams
    Xin Hong, Kezhen Zhang, Aochu Dai +3
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the FORM Model
    Zhihang Li, Wei Zi, Shuai Yang +7
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
    Yuhan Liu, Jose Carrasco, Jens Eisert +1
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{sen2026state,
  title = {{State Synthesis with an NP oracle}},
  author = {Aniruddha Sen},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.02370},
  eprint = {2611.02370},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02370},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - State Synthesis with an NP oracle
AU  - Aniruddha Sen
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.02370
UR  - https://arxiv.org/abs/2611.02370
AB  - In this note, I describe a quantum algorithm that prepares an arbitrary state |ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP oracle, assuming one can directly query entries of the state vector corresponding to |ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP. I provide evidence that NP is the best possible upper bound by showing that any quantum algorithm using a P oracle, or even a P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA search-to-decision problem and unitary synthesis.
ER  -