State Synthesis with an NP oracleResearch Paper
The state synthesis problem, introduced by Aaronson (arXiv:1607.05256), asks how simple a classical Boolean function can be if one fixed quantum algorithm , given oracle access to , is to prepare an arbitrary -qubit state . The circuit of is the same for every state; only may depend on . The question is…