Unitary Synthesis with a PSPACE OracleResearch Paper
The Unitary Synthesis Problem of Aaronson and Kuperberg (AK07, Section 7) asks whether every unitary, computable or not, can be implemented in polynomial time with a suitable classical oracle. The difficulty is that a classical oracle answers questions about strings, while the state to be transformed cannot be read. No circuit with one query of polynomial…