Is random-oracle unitary synthesis impossible for Haar random unitaries?

The question shifts from worst-case to average-case synthesis

The classical Unitary Synthesis Problem, first posed by Aaronson and Kuperberg, asks whether for every unitary U there is a Boolean function f such that U can be computed efficiently given an oracle to f. If true, every hard unitary would sit above an equally hard function; if false, some unitaries stay hard even when all functions are easy. Progress has been modest: the best evidence against it is a lower bound showing that U cannot in general be synthesized efficiently with a single query to f, and that technique was later extended to unitaries synthesizable with two queries.

This paper studies a different, average-case version. Instead of asking about every unitary, it asks whether an algorithm can efficiently implement a Haar random unitary given access to a random Boolean function. The authors call such a procedure a random-oracle unitary synthesis algorithm, and define its error through a coupling between a uniformly random Boolean function f and a Haar random unitary U, requiring the expected diamond distance between the channel computed from f and the unitary channel of U to be at most epsilon.

The motivation is concrete. A pseudorandom unitary in the random oracle model, such as the PFC ensemble, takes in a uniformly random oracle with no structure and is still expected to output a random-looking unitary. Brakerski and Yuen had shown that designing a sufficiently good scalable PRU in the random oracle model would resolve the Unitary Synthesis Problem in the positive direction, because a PRU secure against O(N^2) queries must closely mimic a Haar random unitary. The average-case question isolates exactly the kind of algorithm that route would require.

A sqrt(N)/poly(n) query floor rules out efficient synthesis

The paper's first main result is Theorem 1.2. Suppose A is an n-qubit random-oracle unitary synthesis algorithm with error epsilon, and epsilon is at most 1 minus 1/poly(n), meaning the error is bounded away from 1 by a polynomial factor. Then if k is the number of queries A makes to the random oracle, k must be at least sqrt(N)/poly(n), where N = 2^n.

The unit here is oracle queries, and the denominator is a polynomial in n. The bound is superpolynomial in n, so no efficient algorithm can meet it. The scope condition matters: the theorem applies when the error is even slightly nontrivial, that is, bounded away from 1 by a 1/poly(n) factor. An algorithm that is almost always wrong is not covered.

The authors draw an interpretation from this: any efficient unitary synthesis algorithm must use Boolean functions that are highly structured. They also note, via the results of Brakerski and Yuen, that although there are PRUs in the random oracle model secure against adversaries making o(sqrt(N)) queries, those PRUs cannot be secure against adversaries making O(N^2) queries. That is an inference the paper attributes to combining its bound with prior work, not a separate experiment.

Random oracles carry too few bits to pin down a Haar unitary

The lower bound rests on a counting-style argument. A synthesis algorithm using m total qubits can be written as a circuit W_f = V_k O_f ... O_f V_0, where the V_i are fixed unitaries on m qubits and O_f is the diagonal phase unitary corresponding to a random function f. On an n-qubit input, the algorithm appends m - n ancilla qubits initialized to zero, applies the circuit, traces out the ancillas, and outputs the rest.

The strategy is to show that even though the algorithm draws a large number of random bits from the oracle, only a small number of those bits actually influence the final unitary it computes. If the number of random bits the algorithm effectively depends on is significantly smaller than N^2, then it cannot be simulating a Haar random unitary, because a Haar random unitary on n qubits requires on the order of N^2 real parameters to specify.

The paper first analyzes the simplest case of a single query, where A_f = J^dagger V_1 O_f V_0 J, and assumes for the analysis that the algorithm synthesizes U cleanly, meaning it resets the ancilla qubits to zero before they are traced out. The authors state that this assumption simplifies the analysis and that they later show how to remove it, extending the argument to dirty synthesis. The technical machinery uses representation theory, including Schur's lemma and bounds on dimensions of irreducible representations, to control how much the oracle-dependent phases can move the output.

An O(N)-query secure PRU beats the previous sqrt(N) ceiling

The paper's second main result is Theorem 1.3: there is a PRU in the random oracle model secure against any adversary that makes O(N) queries. This is a construction result, and it directly addresses why earlier PRUs seemed stuck at o(sqrt(N)) query security.

The authors explain that the dominant paradigm for analyzing PRUs focuses on the so-called distinct subspace, which arises when a T-query adversary prepares T standard basis vectors in tensor product and queries the unknown unitary in parallel. When T = o(sqrt(N)), there are tricks to pretend the analysis lives in the distinct subspace, which simplifies matters. Once T = Omega(sqrt(N)), one is forced to consider non-distinct subspaces as well. The paper shows this obstruction was merely technical, not fundamental.

The construction is easy to describe: it computes U = F_n H_n ... F_1 H_1 F_0, where each H_i is a fixed n-qubit unitary and each F_i can be viewed as a query to a separate n-bit random function f_i. The unitary is generated from O~(N) random bits. The PRU is efficient in the sense that it queries the random oracle only poly(n) times, but unlike the PFC ensemble, the authors do not know how to implement it in a computationally efficient manner. They state their belief that this is only a technical barrier and that O(N)-query security should be achievable by PRU algorithms that are both query-efficient and computationally efficient.

Ancilla qubits block query-efficient PRUs past O~(N) queries

The paper's third main result, Theorem 1.4, shows that the O(N) query security of the construction is essentially optimal for query-efficient PRUs in the random oracle model. Fix a constant gamma greater than 0. Suppose there is an n-qubit PRU in the random oracle model secure against T = Omega(N^(1+gamma)) queries. Then if k is the number of queries to the random oracle needed to synthesize the PRU, k must be at least N^(min{gamma,1}/2)/poly(n).

This result interpolates between Theorems 1.2 and 1.3. It rules out security beyond O~(N) queries for query-efficient PRUs in the random oracle model, so the query security achieved by the construction in Theorem 1.3 is optimal up to polynomial factors in n. For PRUs that are T = Omega(N^2)-query secure, it shows the synthesizing algorithm must use roughly N^(1/2) queries, matching the bound in Theorem 1.2.

The mechanism behind this barrier is the ancilla issue. To push beyond O~(N)-query security, a PRU algorithm would need to use more than O~(N) random bits, and the only way to do so with poly(n) queries is to include additional ancilla qubits in the oracle's input register. But querying the ancilla qubits risks creating entanglement between the first n qubits and the ancillas, which would mean the algorithm is no longer computing a unitary on the first n qubits as intended. The authors note this ancilla issue has been a significant barrier even in designing general unitary synthesis algorithms, and it seems especially challenging in the random oracle model, where the form of the oracle cannot be controlled.

Three bounds bracket where random-oracle synthesis and PRUs fail

Read together, the three theorems draw a boundary. Random-oracle unitary synthesis with nontrivial error requires at least sqrt(N)/poly(n) queries, so it is impossible efficiently. A PRU secure against O(N) queries exists and can be built with poly(n) oracle queries, but it is not known to be computationally efficient. And no query-efficient PRU in the random oracle model can be secure against Omega(N^(1+gamma)) queries for any gamma greater than 0.

The comparison that matters is between query security and query efficiency. The construction in Theorem 1.3 achieves O(N)-query security with poly(n) oracle queries, which surpasses the previously best known results that constructed O(sqrt(N))-designs. The lower bound in Theorem 1.4 says that pushing query security beyond O~(N) forces the synthesizing algorithm to use roughly N^(1/2) queries when the target is Omega(N^2)-query security. So the gap between what can be built and what can be built efficiently is the paper's central tension.

The paper also settles in the negative a question Brakerski and Yuen posed, of whether scalable pseudorandom unitaries can be implemented in the ROM-PRU model. In particular, in the ROM-PRU model no Omega(N^(1+gamma)) unitary design on n qubits, where N = 2^n, can be efficiently achieved for any gamma greater than 0. On the other hand, the paper constructs an O(N)-design in poly(n) queries in the same model.

The impossibility is specific to random, unstructured oracles

The lower bounds are stated for algorithms that receive a uniformly random Boolean function as the oracle. The paper is explicit that this is a restriction: a unitary synthesis algorithm in the general setting is given query access to a Boolean function f_U that may be highly structured and may depend on the unitary U in arbitrary and complicated ways. The Bernstein-Vazirani-based synthesis algorithm, for example, takes an N x N unitary, represents it as a bitstring of length O~(N^2), takes the 2^O~(N^2)-bit-long Hadamard encoding of that string, and uses that highly structured function as f_U.

So the impossibility result does not say that no unitary can be synthesized from any Boolean function. It says that synthesis cannot succeed when the function is random and unstructured. The authors state this directly: any efficient unitary synthesis algorithm must use Boolean functions which are highly structured.

A second scope condition is the error threshold. Theorem 1.2 requires epsilon at most 1 minus 1/poly(n). The bound is about query complexity, not about computational time beyond the query count, and the clean-synthesis assumption used in the single-query analysis is later removed by extending the argument to dirty synthesis. The O(N)-query PRU construction is query-efficient but not known to be computationally efficient, a limitation the authors flag next to that result rather than treating it as a final verdict.

The decisive question is whether O(N) security can be made efficient

The paper's most decision-relevant comparison is not simply whether random-oracle unitary synthesis is possible. It is the gap between query security and query efficiency. Theorem 1.3 shows that O(N)-query security is achievable with poly(n) oracle queries, surpassing the previous O(sqrt(N))-designs. Theorem 1.4 shows that no query-efficient PRU in the random oracle model can be secure against Omega(N^(1+gamma)) queries for any gamma greater than 0, and that reaching Omega(N^2)-query security forces roughly N^(1/2) queries.

That places the open question precisely. The construction in Theorem 1.3 is efficient in oracle queries but not known to be computationally efficient. The authors state their belief that this is only a technical barrier and that O(N)-query security should be achievable by PRU algorithms that are both query-efficient and computationally efficient. If that belief is correct, the ancilla barrier is a technical obstacle rather than a fundamental one. If it is not, then the O(N) ceiling for query-efficient PRUs stands as the real limit.

For readers tracking the Unitary Synthesis Problem, the practical threshold is this: the impossibility result applies to random, unstructured oracles, so structured Boolean functions remain the only viable route to efficient synthesis. The PRU route that Brakerski and Yuen identified would require security against O(N^2) queries, and this paper shows that no query-efficient ROM-PRU can get there. The priority is therefore to determine whether the O(N)-query secure construction can be made computationally efficient, because that is the single step separating the current state from a scalable PRU in the random oracle model.

Sources used in this answer