Vinod Vaikuntanathan

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor $n$-bit integers of the form $P^2 Q$ with $\log Q = \Theta(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (specifically, $\widetilde{O}(\log Q)$) using $\widetilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

In this work, we introduce a new toolkit for analyzing \emph{cloning games}, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. This framework allows us to analyze a new cloning game based on \emph{binary phase states}. Our results provide evidence that these games may be able to overcome important limitations of previous candidates based on BB84 states and subspace coset states: in a model where the adversaries are restricted to making a single oracle query, we show that the binary phase variant is $t$-copy secure when $t=o(n/\log n)$. Moreover, for constant $t$, we obtain the \emph{first} optimal bounds of $O(2^{-n})$, asymptotically matching the value attained by a trivial adversarial strategy. We also show a worst-case to average-case reduction which allows us to show the same quantitative results for the new and natural notion of \emph{Haar cloning games}. Our analytic toolkit, which we believe will find further applications, is based on binary subtypes and uses novel bounds on the operator norms of block-wise tensor products of matrices. To illustrate the effectiveness of these new techniques, we present two applications: first, in black-hole physics, where our asymptotically optimal bound offers quantitative insights into information scrambling in idealized models of black holes; and second, in unclonable cryptography, where we (a) construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries, and (b) propose and provide evidence for the security of multi-copy unclonable encryption schemes.

The development of quantum codes with good error correction parameters and useful sets of transversal gates is an area of major interest in quantum error correction. Abundant prior works have studied transversal gates which are restricted to acting on all logical qubits simultaneously. In this work, we study codes that support transversal gates which induce addressable logical gates, i.e., the logical gates act only on logical qubits of our choice. As we consider scaling from low-rate to high-rate codes, the study and design of low-overhead, addressable logical operations presents an important problem for both theoretical and practical purposes. In this work, we construct the first quantum codes to support transversally addressable non-Clifford gates. Concretely, given any three logical qubits across one or multiple codeblocks, one can execute the logical CCZ on those qubits via a depth-one physical circuit of CCZ gates. We present a simple, explicit construction based on Reed-Solomon codes that is nearly asymptotically good, and a more involved, asymptotically good construction based on transitive, iso-orthogonal algebraic geometry codes. We go on to develop a powerful theory of quantum codes supporting a rich class of transversally addressable gates in the Clifford hierarchy, going far beyond just the CCZ gate. We call this framework addressable orthogonality, and show that it can be used to construct asymptotically good quantum codes supporting an arbitrary product of multiply-controlled Z gates transversally and addressably, enabling major adaptivity to particular algorithms. Our constructions mark the first quantum codes to support any multi-qubit gate transversally and addressably. Accordingly, our results have major implications for the general addressabilitiy problem in error correction. This is a merged submission based on arXiv:2502.01864 and arXiv:2507.05392.

Random classical linear codes are widely believed to be hard to decode, exponentially so at constant coding rate. If the rate vanishes asymptotically sufficiently rapidly, slightly sub-exponential decoding algorithms are known. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any coding rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. Our work also demonstrates several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity.

Abstract MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT.