  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 bound for unitary synthesis. We show
that there exist unitaries $U$ such that no quantum polynomial-time oracle
algorithm $A^f$ can implement $U$, even approximately, if it only makes one
(quantum) query to $f$. Our approach also has implications for quantum
cryptography: we prove (relative to a random oracle) the existence of quantum
cryptographic primitives that remain secure against all one-query adversaries
$A^{f}$. Since such one-query algorithms can decide any language, solve any
classical search problem, and even prepare any quantum state, our result
suggests that implementing random unitaries and breaking quantum cryptography
may be harder than all of these tasks.
  To prove this result, we formulate unitary synthesis as an efficient
challenger-adversary game, which enables proving lower bounds by analyzing the
maximum success probability of an adversary $A^f$. Our main technical insight
is to identify a natural spectral relaxation of the one-query optimization
problem, which we bound using tools from random matrix theory.
  We view our framework as a potential avenue to rule out polynomial-query
unitary synthesis, and we state conjectures in this direction.
