Explicit non-poly-local unitaries: exhibit a unitary family beyond polynomial-size quantum circuits, and locate the ancilla/dilation boundary (from Freedman, Poly-Locality in Quantum Computing, 2002)

Freedman's notion of poly-locality isolates the unitary transformations of an n-qubit tensor-product space that polynomial-depth quantum circuits can approximate - on standard physical grounds, precisely the transformations nature supplies. Counting (volume) arguments show that almost every unitary lies far outside this class, yet since the source paper posed the question in 2002 no explicit family of unitaries has been exhibited and proven to be non-approximable by polynomial-size circuits; the question is the quantum analogue of the classical explicit circuit lower bound problem, which it contains for permutation-type families. The source pairs this core with a companion question: whether dilating an operator as $T\otimes\mathrm{id}$, or allowing ancillas, can systematically convert a non-poly-local operator into a poly-local one. No unconditional explicit superpolynomial quantum circuit lower bound is known in the unrestricted circuit model, and the ancilla/dilation boundary is undetermined. The problem is open.

Background

In the quantum circuit model, information is stored in a tensor product of $n$ two-level systems (qubits), $(\mathbb{C}^2)^{\otimes n}$, and a computation is a unitary transformation assembled from elementary gates, each acting nontrivially on only one, two, or three tensor factors at a time. Freedman calls a unitary poly-local if, for every target accuracy $\epsilon$, it can be approximated - up to a global phase $e^{i\theta}$, which is physically unobservable, and in the operator norm $\|A\|=\sup_{\|v\|=1}\|Av\|$ - by a composition of $\mathrm{poly}(n,\log(1/\epsilon))$ elementary gates. (Unless a sub-question states otherwise, 'poly-local' is read as allowing polynomially many ancilla qubits that are initialized to a fixed state and returned to it; the no-ancilla variant, used in the companion clause, is the more restrictive reading, so that 'non-poly-local' under it is a strictly weaker hardness claim.) By the Solovay-Kitaev theorem (any fixed finite universal gate set can simulate any unitary on a fixed number of qubits with overhead only polylogarithmic in $1/\epsilon$), the choice of universal gate set changes this notion by at most polynomial factors, and polynomial-depth circuits define the complexity class $BQP$ of problems efficiently solvable by a quantum computer. The physical motivation recounted in the source is that Hamiltonians built from few-body terms - the locality structure of real interactions - generate poly-local evolutions, so poly-locality marks the boundary between what a quantum computer, or nature, can implement and what it cannot.

A counting (volume) argument shows that only a tiny fraction of the unitary group $U(2^n)$ lies within any fixed constant operator-norm distance of a polynomial-size circuit: the set of such circuits is far too small to cover the group. Yet, as the source remarks, this argument is as nonconstructive as the proof that most real numbers are transcendental, and no explicit family of unitaries was known to be provably far from every polynomial-size circuit. The same gap is famous classically: counting shows that most Boolean functions need exponentially many gates, but no explicit function has been proven to require superpolynomial - even superlinear - circuit size; and for quantum families that act as permutations of the computational basis, a quantum circuit lower bound implies the corresponding classical one.

Two of the source's own secondary results frame the core. First, the paper proves that the standard orthogonal discrete wavelet transforms (transforms built from banded, cyclically periodic quadrature-mirror filter matrices - the matrices implementing one step of the pyramid algorithm that splits a signal into a smoothed part and detail parts at dyadic scales, i.e. scales that are powers of two) are poly-local without ancillas (extra workspace qubits initialized to a fixed state and returned to it). Second, it observes that adjoining an oracle - a 'super-gate' $O_n$ that may act on all $n$ qubits at once but whose matrix entries are computable in $\mathrm{poly}(n)$ time ('locally-poly') - already destroys one-way functions (functions easy to compute but hard to invert): the permutation oracle with entries $\delta_{f(i),j}$ (the matrix sending the basis vector indexed by $i$ to the one indexed by $f(i)$) inverts any polynomial-time bijection in a single query; consequently, whenever such a bijection is genuinely hard to invert - the one-way case - this inverting oracle is necessarily non-poly-local, since a poly-local approximation of it would place inversion inside $BQP$. The companion clause of the core records the source's conjecture that the ancilla/dilation freedom is real: it credits an observation of Michael Nielsen (private communication, and the simulation chapter of the Nielsen-Chuang textbook) that exponentials of Hamiltonians which are sums of polynomially many product terms become efficiently simulable once ancillas are allowed, while their ancilla-free status is unclear.

The later literature developed two main lines on this core. Michael Nielsen's geometric program (2005) recast the minimal size of an ancilla-free circuit exactly implementing a given unitary as the length of a minimal geodesic (shortest path) for a Finsler metric - a rule that assigns a length to each direction of motion on the unitary group, generalizing Riemannian distance - as a direct attempt to prove explicit lower bounds; it yielded a framework (including, for unitaries diagonal in the computational basis, an equivalence between the minimal-geodesic question and exponentially large instances of the closest-vector-in-a-lattice problem, together with exponential geodesic length for all but a doubly exponentially small fraction of such unitaries) but no explicit superpolynomial lower bound, and its later life has been mostly in holographic complexity (the study of quantum circuit complexity through conjectured dual gravitational descriptions of quantum many-body systems). The modern unitary-synthesis line, begun by Aaronson and Kuperberg in 2007, asks the complementary oracle question of whether every $n$-qubit unitary is computable by an efficient quantum algorithm granted oracle access to an arbitrary Boolean function depending on the unitary; the strongest lower bounds to date (2023-2026) rule out one-query and 1.5-query synthesis for Haar-random (uniformly random) unitaries and for certain randomly drawn structured families, and connect the problem to pseudorandom unitaries (efficient circuit families statistically indistinguishable from Haar-random ones). Neither line has produced, or removed the need for, an explicit unconditional circuit-size lower bound.

Problem Statement

The problem has a core and a source-paired companion clause, which together serve one objective: to exhibit the first concrete member of the non-poly-local world and to show that its hardness is intrinsic under the embedding and ancilla freedom that the circuit model normally enjoys.

Core (explicit non-poly-local unitaries, from the source's introduction). Exhibit an explicit family of unitaries $T_n\in U(2^n)$ - 'explicit' meaning that the entries of $T_n$ are computable in $\mathrm{poly}(2^n)$ time, or are specified by an equally concrete closed-form description - together with a constant $\epsilon_0>0$, and prove that $T_n$ is not poly-local: for every polynomial $p$ there exists $n_0$ such that for all $n\geq n_0$, every quantum circuit of size at most $p(n)$ built from a fixed finite universal gate set (allowing polynomially many ancilla qubits that are initialized to a fixed state and returned to it, unless the no-ancilla variant is explicitly stated as the target) differs from $T_n$ by at least $\epsilon_0$ in operator norm, up to a global phase.

Companion clause (ancilla/dilation boundary, stated in the source). In this clause $H=(\mathbb{C}^2)^{\otimes n}$ and $H^+=H\otimes H'$ is a larger space obtained by adjoining an auxiliary register $H'$ of at most polynomially many qubits (the same ancilla budget that the Core fixes); throughout the clause 'poly-local circuits on $H$' is read in the no-ancilla variant - circuits acting on the $n$ qubits of $H$ alone, with no additional workspace initialized to a fixed state - since the extra register of $H^+$ is exactly the ancilla/dilation resource whose power the clause tests. Determine whether the freedom to enlarge the Hilbert space can convert non-poly-locality into poly-locality: does there exist a unitary operator $T$ on $H$ that is not approximable by poly-local circuits on $H$, while its extension $T\otimes\mathrm{id}$ on the larger space $H^+$ is so approximable? The hardness is to be intrinsic to the family: 'non-poly-local' holds of the exhibited family itself under the ancilla and dilation conventions stated above, rather than as an artifact of those conventions; the complementary question is whether poly-locality of $T\otimes\mathrm{id}$ implies poly-locality of $T$ up to polynomial overhead.

References

1. Michael H. Freedman, Poly-Locality in Quantum Computing, Foundations of Computational Mathematics 2, 145-154 (2002), DOI 10.1007/s102080010020, https://doi.org/10.1007/s102080010020 (preprint arXiv:quant-ph/0001077, https://arxiv.org/abs/quant-ph/0001077)
2. Michael A. Nielsen, A geometric approach to quantum circuit lower bounds, arXiv:quant-ph/0502070 (2005), https://arxiv.org/abs/quant-ph/0502070
3. Scott Aaronson and Greg Kuperberg, Quantum versus classical proofs and advice, arXiv:quant-ph/0604056 (2006; conference version CCC 2007, where the unitary synthesis problem was posed; journal version Theory of Computing 3, 129-157, 2007), https://arxiv.org/abs/quant-ph/0604056
4. Alex Lombardi, Fermi Ma, and John Wright, A one-query lower bound for unitary synthesis and breaking quantum cryptography, arXiv:2310.08870 (2023; conference version STOC 2024), https://arxiv.org/abs/2310.08870
5. Eric Huang, A 1.5-Query Lower Bound for the Unitary Synthesis Problem, arXiv:2508.13215 (2025), https://arxiv.org/abs/2508.13215
6. Fangqi Dong, Alex Lombardi, and Fermi Ma, Explicit Separations for One-Query Unitary Synthesis, arXiv:2607.26478 (2026), https://arxiv.org/abs/2607.26478
7. Zvika Brakerski and Henry Yuen, On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem, arXiv:2605.09957 (2026), https://arxiv.org/abs/2605.09957
8. Shira Chapman and Giuseppe Policastro, Quantum Computational Complexity - From Quantum Information to Black Holes and Back, arXiv:2110.14672 (2021), https://arxiv.org/abs/2110.14672
9. I. Garcia-Mata, O. Giraud, and B. Georgeot, Quantum computation of multifractal exponents through the quantum wavelet transform, Physical Review A 79, 052321 (2009), arXiv:0901.0108, https://arxiv.org/abs/0901.0108
10. Mohsen Bagherimehrab and Alan Aspuru-Guzik, Efficient Quantum Algorithm for All Quantum Wavelet Transforms, arXiv:2309.09350 (2023; journal version Quantum Science and Technology 9, 035010, 2024), https://arxiv.org/abs/2309.09350
11. Amir Fijany and Colin P. Williams, Quantum Wavelet Transforms: Fast Algorithms and Complete Circuits, arXiv:quant-ph/9809004 (1998), https://arxiv.org/abs/quant-ph/9809004
12. Andreas Klappenecker, Wavelets and Wavelet Packets on Quantum Computers, arXiv:quant-ph/9909014 (1999), https://arxiv.org/abs/quant-ph/9909014
13. David P. DiVincenzo, The Physical Implementation of Quantum Computation, Fortschritte der Physik 48, 771 (2000), arXiv:quant-ph/0002077, https://arxiv.org/abs/quant-ph/0002077
14. Adam Bouland and Maris Ozols, Trading inverses for an irrep in the Solovay-Kitaev theorem, arXiv:1712.09798 (2017; journal version Proceedings of TQC 2018, LIPIcs 111, 6:1-6:15), https://arxiv.org/abs/1712.09798
15. Adam Bouland and Tudor Giurgica-Tiron, Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm, arXiv:2112.02040 (2021), https://arxiv.org/abs/2112.02040
16. Greg Kuperberg, Breaking the cubic barrier in the Solovay-Kitaev algorithm, arXiv:2306.13158 (2023), https://arxiv.org/abs/2306.13158
17. Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram, Quantum learning algorithms imply circuit lower bounds, arXiv:2012.01920 (2020), https://arxiv.org/abs/2012.01920
18. Nai-Hui Chia, Daniel Liang, and Fang Song, Quantum State Learning Implies Circuit Lower Bounds, arXiv:2405.10242 (2024), https://arxiv.org/abs/2405.10242
19. Natalie Parham, Quantum circuit lower bounds in the magic hierarchy, arXiv:2504.19966 (2025), https://arxiv.org/abs/2504.19966
20. Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000; 10th-anniversary edition 2012), DOI 10.1017/CBO9780511976667, https://doi.org/10.1017/cbo9780511976667
21. Honghuai Fang, Variable-Cliff Nielsen Geometry and an Exponent -4/3 Lower Bound for the Infinite-Cliff Diameter, arXiv:2609.03323 (2026), https://arxiv.org/abs/2609.03323