2026-10-11T04:21:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25348 2026-03-19T12:03:51Z ddc:004 open_access

Random Unitaries in Constant (Quantum) Time Foxman, Ben Parham, Natalie Vasconcelos, Francisca Yuen, Henry Quantum Information Pseudorandomness Circuit Complexity Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ben Foxman and Natalie Parham and Francisca Vasconcelos and Henry Yuen 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.61 urn:nbn:de:0030-drops-253481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61 eng https://creativecommons.org/licenses/by/4.0/legalcode