A one-query lower bound for unitary synthesis and breaking quantum cryptography

ePrint Report: A one-query lower bound for unitary synthesis and breaking quantum cryptography

Alex Lombardi, Fermi Ma, John Wright

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function?

In this work, we prove a one-query lower …

alex algorithm breaking cryptography eprint report john oracle problem quantum quantum cryptography qubit query report