Papers

Shor's factoring algorithm guarantees a success probability of at least one half for any fixed modulus N = pq with distinct primes p and q. We show that this guarantee does not extend to the asymptotic regime. As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)^x form a non-tight family of probability spaces, and the probability weight associated with successful bases, proportional to p(success | a', N) p(a' | N), decays as 1/phi(N). The ensemble of uniform measures {mu_N} therefore admits no weak limit, implying an asymptotic loss of ergodicity. Monte Carlo simulations up to N <= 10^6 confirm this decay and the absence of a stationary success probability. These results demonstrate that the "expected polynomial time" in order finding is only locally defined: no global expectation exists once the arithmetic domain expands. The asymptotic vanishing of success probability explains the empirical absence of large-N implementations of Shor's algorithm and sets a fundamental limit on the scalability of quantum factoring.

The rapid decay of target signal strength with distance from the sensor presents a key challenge in nanoscale magnetic sensing with nitrogen-vacancy (NV) centers in diamond, limiting both sensitivity and spatial resolution. Here we introduce a strategy to overcome this limitation by using radical anions formed from rhodamine-derived dyes as reporter spins localized to the diamond surface. These radicals, generated through photoreduction, are optically identifiable and stable on timescales exceeding an hour. We experimentally demonstrate their coherent manipulation and detection using single, shallow NV centers for readout. We observe heterogeneity in the local magnetic environments of the photoactivated spins from site to site, likely due to variations in inter-radical couplings across our measurements. Looking forward, our approach enables correlative nanoscale magnetic and optical imaging, and opens new pathways toward single-molecule magnetic resonance studies.

The generation of entangled photons through Spontaneous Parametric Down-Conversion (SPDC) is a critical resource for many key experiments and technologies in the domain of quantum optics. Historically, SPDC was limited to the generation of photon pairs. However, the use of the strong nonlinearities in circuit quantum electrodynamics has recently enabled the observation of Three-Photon SPDC (3P-SPDC). Despite great interest in the entanglement structure of the resultant states, entanglement between photon triplets produced by a 3P-SPDC source has still has not been confirmed. Here, we report on the observation of genuine tripartite non-Gaussian entanglement in the steady-state output field of a 3P-SPDC source consisting of a superconducting parametric cavity coupled to a transmission line. We study this non-Gaussian tripartite entanglement using an entanglement witness built from three-mode correlation functions, and observe a maximum violation of the bound by 23 standard deviations of the statistical noise. Furthermore, we find strong agreement between the observed and the analytically predicted scaling of the entanglement witness. We then explore the impact of the temporal function used to define the photon mode on the observed value of the entanglement witness.

There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric barrier theorem for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible “gap” between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting.

We initiate the development of a new language and theory for quantum music, to which we refer as Quantum Concept Music (QCM). This new music formalism is based on Categorical Quantum Mechanics (CQM), and more specifically, its diagrammatic incarnation Quantum Picturalism (QPict), which is heavily based on ZX-calculus. In fact, it is naturally inherited from CQM/QPict. At its heart is the explicit notational representation of relations that exist within and between the key concepts of music composition, performance, and automation. QCM also enables one to directly translate quantum phenomena into music compositions in a both intuitively obvious, rigorous and mechanical manner. Following this pattern, we propose a score for musicians interacting like a Bell-pair under measurement, and outline examples of how it could be live performed. While most of the Western classical music notation has heavily relied on linear representation of music - which does not always adequately capture the nature of music - our approach is distinct by highlighting the fundamental relational dimension of music. In addition, this quantum-based technique not only influences the music at the profound level of composition, but also has a direct impact on a live performance, and also provides a new template for automating music, e.g.~in the context of AI-generation. All together, we initiate the creation of new music formalism that is powerful and efficient in capturing the interactive nature of music, both in terms of internal and external interactions, and goes beyond the boundaries of Western classical music notation, which allows to use it in many different genres and directions.

Optically levitated and cooled nanoparticles are a new quantum system whose application to the creation of non-classical states of motion and quantum limited sensing is fundamentally limited by recoil and bulk heating. We study the creation of stable 3D optical traps using optical cylindrically polarized vortex beams with radial and azimuthal polarization and show that a significant reduction in recoil heating by up to an order of magnitude can be achieved when compared with conventional single Gaussian beam tweezers. Additionally these beams allow trapping of larger particles outside the Rayleigh regime using both bright and dark tweezer trapping with reduced recoil heating. By changing the wavelength of the trapping laser, or the size of the particles, non-linear and repulsive potentials of interest for the creation of non-classical states of motion can also be created.

Measurement of a charge qubit via point contacts with complex internal structures is considered. In this context, a fully formalized derivation of the many-body wave function method is presented, together with the corresponding master equations for point contacts possessing an arbitrary number of internal states. The focus is placed on the current noise power spectrum and its dependence on the qubit dynamics and the point contact parameters.

We present an exact solution for entanglement entropy for the real-time dynamics following a quench from a thermal pure quantum (TPQ) state in a free-fermion system. In contrast to the usual linear growth and saturation behavior, the entanglement entropy exhibits a characteristic double-plateau structure. We establish this behavior through three complementary approaches: an exact conformal field theory calculation on the Klein bottle, finite-size Gaussian-state simulations, and a quasiparticle picture that becomes quantitatively accurate in the scaling regime.

We construct a publicly-verifiable non-interactive zero-knowledge argument system for QMA with the following properties. 1. Transparent setup. Our protocol only requires a uniformly random string (URS) setup. The only prior publicly-verifiable NIZK for QMA (Bartusek and Malavolta, ITCS 2022) requires an entire obfuscated program as the common reference string. 2. Extractability. Valid QMA witnesses can be extracted directly from our accepting proofs. That is, we obtain a publicly-verifiable non-interactive argument of quantum knowledge, previously only known in a privately-verifiable setting (Coladangelo, Vidick, and Zhang, CRYPTO 2020). Our construction introduces a novel ZX QMA verifier with "strong completeness" and builds upon the coset state authentication scheme from (Bartusek, Brakerski, and Vaikuntanathan, STOC 2024) within the context of QMA verification. Along the way, we establish new properties of the authentication scheme. The security of our construction rests on the heuristic use of a post-quantum indistinguishability obfuscator. Rather than rely on the full-fledged classical oracle model (i.e. ideal obfuscation), we isolate a particular game-based property of the obfuscator that suffices for our proof, which we dub the evasive composability heuristic. As an additional contribution, we study a general method for replacing heuristic use of obfuscation with heuristic use of hash functions in the post-quantum setting. In particular, we establish security of the ideal obfuscation scheme of Jain, Lin, Luo, and Wichs (CRYPTO 2023) in the quantum pseudorandom oracle model (QPrO), which can be heuristically instantiated with a hash function. This gives us NIZK arguments of quantum knowledge for QMA in the QPrO, and additionally allows us to translate several quantum-cryptographic results that were only known in the classical oracle model to results in the QPrO.

Gradient-based optimization is a key ingredient of variational quantum algorithms, with applications ranging from quantum machine learning to quantum chemistry and simulation. The parameter-shift rule provides a hardware-friendly method for evaluating gradients of expectation values with respect to circuit parameters, but its applicability is limited to circuits whose gate generators have a particular spectral structure. In this work, we present a generalized framework that, with optimal minimum measurement overhead, extends parameter shift rules beyond this restrictive setting to encompass basically arbitrary gate generator, possibly made of complex multi-qubit interactions with unknown spectrum and, in some settings, even infinite dimensional systems such as those describing photonic devices or qubit-oscillator systems. Our generalization enables the use of more expressive quantum circuits in variational quantum optimization and enlarges its scope by harnessing all the available hardware degrees of freedom.

A key issue with existing quantum advantage experiments is that their verification requires exponential classical time. In this work, we address this challenge by designing a new proposal—Hidden Code Sampling—with efficient classical verification. We use properties of quantum error correction to build an experiment that is "conditionally peaked": conditioned on a subset of qubits, the distribution on another subset is peaked. We give evidence for the classical intractability of this protocol by showing complexity-theoretic hardness of classical simulation, putting our scheme on par with other quantum advantage schemes. A major hurdle in instantiating the scheme concerns distinguishing between two noise channels, one involving local coherent noise and the other involving local Pauli noise. We identify algebraic properties of the underlying codes that enable an efficient distinguisher and construct an explicit code family satisfying these properties while preserving the hardness guarantees. We provide further evidence for soundness of our verification tests by proving an exponential query lower bound for classical algorithms that pass our verification tests in a black-box model.

Bound electron-hole pairs in semiconductors known as excitons are the subject of intense research due to their potential for optoelectronic devices and applications, especially in the realm of two-dimensional materials. While the properties of free excitons in these systems are well understood, a general description of the interactions between these quasiparticles is complicated due to their composite nature, which leads to important exchange processes that can take place between the identical fermions of different excitons. In this work, we employ a variational approach to study interactions between Wannier excitons and obtain an effective interaction potential between two ground-state excitons in a system of spin-degenerate electrons and holes. This potential is in general nonlocal in position space and depends on the combined spin configurations of the electrons and holes. When particularized to the case of hydrogen-like excitons with a heavy hole, this potential becomes local and exactly reproduces the Heitler-London result for two interacting hydrogen atoms. Thus, our result can be interpreted as a generalization of the Heitler-London potential to the case of arbitrary masses. We also show how including corrections due to excited states into the theory results in a van der Waals potential at large distances, which is expected due to the induced dipole-dipole nature of the interactions. Our approach is also applicable to more complicated systems with nonhydrogenic exciton series, such as layered semiconductors with Rytova-Keldysh interactions. Additionally, we use a path-integral formalism to develop a many-body theory for a dilute gas of excitons, resulting in an excitonic action that formally includes many-body interactions between excitons. While in this approach the field representing the excitons is exactly bosonic, we clarify how the internal exchange processes arise in...

We introduce TeMFpy, a Python library for converting fermionic mean-field states to finite or infinite matrix product state (MPS) form. TeMFpy includes new, efficient, and easy-to-understand algorithms for both Slater determinants and Pfaffian states. Together with Gutzwiller projection, these also allow the user to build variational wave functions for various strongly correlated electron systems, such as quantum spin liquids. We present all implemented algorithms in detail and describe how they can be accessed through TeMFpy, including full example workflows. TeMFpy is built on top of TeNPy and, therefore, integrates seamlessly with existing MPS-based algorithms.

We study the hard-core Fermi-Hubbard model in the crossover between square and triangular lattices near half-filling. As was recognized by Nagaoka in the 1960s, on the square lattice the presence of a single hole leads to ferromagnetic spin ordering. On the triangular lattice, geometric frustration instead leads to a spin-singlet ground state, which can be associated with a 120-degree spiral order. On lattices which interpolate between square and triangular, there is a phase transition at which the ferromagnetic order becomes unstable to a spin spiral. We model this transition, finding the exact location of the spin-spiral instability.

We introduce several dynamical schemes that take advantage of mid-circuit measurement and nearest-neighbor gates on a lattice with maximum vertex degree three to implement topological codes and perform logic gates between them. We first review examples of Floquet codes and their implementation with nearest-neighbor gates and ancillary qubits. Next, we describe implementations of these Floquet codes that make use of the ancillary qubits to reset all qubits every measurement cycle. We then show how switching the role of data and ancilla qubits allows a pair of Floquet codes to be implemented simultaneously. We describe how to perform a logical Clifford gate to entangle a pair of Floquet codes that are implemented in this way. Finally, we show how switching between the color code and a pair of Floquet codes, via a depth-two circuit followed by mid-circuit measurement, can be used to perform syndrome extraction for the color code.

Decoding stabilizer codes such as the surface and toric codes involves evaluating free-energy differences in a disordered statistical mechanics model, in which the randomness comes from the observed pattern of error syndromes. We study the statistical distribution of logical failure rates across observed syndromes in the toric code, and show that, within the coding phase, logical failures are predominantly caused by exponentially unlikely syndromes. Therefore, postselecting on not seeing these exponentially unlikely syndrome patterns offers a scalable accuracy gain. In general, the logical error rate can be suppressed from $p_f$ to $p_f^b$, where $b \geq 2$ in general; in the specific case of the toric code with perfect syndrome measurements, we find numerically that $b = 3.1(1)$. Our arguments apply to general topological stabilizer codes, and can be extended to more general settings as long as the decoding failure probability obeys a large deviation principle.

Modular architectures offer a scalable path toward fault-tolerant quantum computing by interconnecting smaller quantum processing units (QPUs) provided that high-rate, fault-tolerant interfaces can be realized across modules. We present a comprehensive analysis and comparison of known and new methods for establishing such interfaces, including lattice surgery, transversal gates, and novel grow-and-distil protocols based on code growing and logical distillation. Using the surface code, we identify optimal interface strategies across a wide range of hardware parameters, such as gate fidelities, entangling rates, and memory resources, and estimate the requirements to achieve logical error rates of $10^{-6}$ and $10^{-12}$. Our results establish when the interface become a bottleneck in the computation and provide guidance for experimental implementations with superconducting, atomic, and solid-state hardware.

We study the effects of the intertube dipole-dipole interactions (DDI) in recent experiments with arrays of nearly integrable one-dimensional (1D) dipolar Bose gases of $^{162}$Dy atoms. An earlier theoretical modeling ignored those interactions, which we include here via a modification of the 1D confining potentials. We investigate the effects of the intertube DDI both during the state preparation and during the measurements of the rapidity distributions. We explore how the strength of the contact interactions and the magnetic field angles modify the intertube DDI corrections. We find that those corrections slightly change both the properties of the equilibrium state and the rapidity measurements. Remarkably, however, the changes nearly cancel each other, resulting in measured rapidity distributions that are very close to those predicted in the absence of the intertube DDI.

Bivariate bicycle codes are promising candidates for high-threshold, low-overhead fault-tolerant quantum memories. Meanwhile, color codes are the most prominent self-dual CSS codes, supporting transversal Clifford gates that have been demonstrated experimentally. In this work, we combine these advantages and introduce a broad family of self-dual bivariate bicycle codes. These codes achieve higher encoding rates than surface and color codes while admitting transversal CNOT, Hadamard, and $S$ gates. In particular, we enumerate weight-8 self-dual bivariate bicycle codes with up to $n \leq 200$ physical qubits, realized on twisted tori that enhance code distance and improve stabilizer locality. Representative examples include codes with parameters $[[n,k,d]]$: $[[16,4,4]]$, $[[40,6,6]]$, $[[56,6,8]]$, $[[64,8,8]]$, $[[120,8,12]]$, $[[152,6,16]]$, and $[[160,8,16]]$.

We consider a pair of causally independent processes, modelled as the tensor product of two channels, acting on a possibly correlated input to produce random outputs X and Y. We show that, assuming the processes produce a sufficient amount of randomness, one can extract uniform randomness from X and Y. This generalizes prior results, which assumed that X and Y are (conditionally) independent. Note that in contrast to the independence of quantum states, the independence of channels can be enforced through spacelike separation. As a consequence, our results allow for the generation of randomness under more practical and physically justifiable assumptions than previously possible. We illustrate this with the example of device-independent randomness amplification, where we can remove the constraint that the adversary only has access to classical side information about the source.

Is the usual treatment of axion dark matter as a classical field reliable? We show that the answer is subtle: the axion field could well be in a quantum state that has no complete classical description, but realistic detectors cannot tell the difference. To see this, we solve a fully quantum model of axion detection using quantum optics techniques. We show that intrinsically quantum effects are washed out by mode averaging or small amounts of noise, and significantly suppressed by the weakness of the axion coupling. Our work exemplifies that there should always be a classical analog for axion dark matter effects, extends to other wave (ultralight) dark-matter candidates, and gives a general method to compute the effects of exotic dark-matter states.

Routing is the task of permuting qubits in such a way that quantum operations can be parallelized maximally, given constraints on the hardware geometry. When simulating fermions in the Jordan-Wigner encoding with qubits, a one-dimensional nearest-neighbor-connected geometry is effectively imposed on the system, independently of the underlying hardware, which means that naively, an $O(N)$ depth routing overhead is incurred. Recently, Maskara et al. [arXiv:2509.08898] demonstrated that this routing overhead can be reduced to $O(\log N)$ by decomposing general fermion routing into $O(\log N)$ interleave permutations of depth $O(1)$, using $\Theta(N)$ ancillary qubits and employing measurements and feedforward. Here, we exhibit an alternative construction that achieves the same asymptotic performance. We also generalize the result in two ways. Firstly, we show that fermion routing can be performed in depth $O(\log^2 N)$ without ancillas, measurements, or feedforward. Secondly, we construct efficient mappings with $O(\log^2 N)$ depth between all product-preserving ternary tree fermionic encodings, thereby showing that fermion routing in any such encoding can be done efficiently. While these results assume all-to-all connectivity, they also imply upper bounds for fermion routing in devices with limited connectivity by multiplying the fermion routing depth by the worst-case qubit routing depth.

The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple weak learners-hypotheses that are only slightly better than random guessing-into a single strong learner that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.

Vacuum cavity control of quantum materials is the engineering of quantum materials systems through electromagnetic zero-point fluctuations. In this work we articulate a generic mechanism for vacuum optical control of correlated electronic order: Casimir control, where the zero-point energy of the electromagnetic continuum, the Casimir energy, depends on the properties of the material system. To assess the experimental viability of this mechanism we focus on the Casimir stabilization of fluctuating nematic order. In nematic Fermi liquids, different orientations of the electronic order are often energetically degenerate. Thus, while local domains of fixed orientation may form, thermal disordering inhibits long range order. By engineering the electromagnetic environment of the electronic system, however, we show that the Casimir energy can be used as a tool to preferentially stabilize particular orientations of the nematic order. As a concrete example, we examine the interplay between a birefringent crystal – which sources an anisotropic electromagnetic environment – and a quantum Hall stripe system, an archetypal nematic Fermi fluid. We show that for experimentally feasible setups, the anisotropy induced by the orientation dependent Casimir energy can be $10^4$ times larger than other mechanisms known to stabilize quantum Hall stripes. This finding convincingly implies that our setting may be realized with currently available experimental technology. Having demonstrated that the Casimir energy can be used to stabilize fluctuating nematic order, we close by discussing the implications for recent terahertz cavity experiments on quantum Hall stripes, as well as pave the road towards broader Casimir control of competing correlated electronic phases.

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” PoQ is to simply assume an average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQ that actually rely on quantum hardness assumptions, as these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

The quantum control of spin-correlated radical pairs (SCRPs) holds promise for the targeted manipulation of magnetic field effects, with potential applications ranging from the design of noise-resilient quantum information processors to genetically encodable quantum sensors. However, achieving precise handles over the intricate interplay between coherent electron spin dynamics and incoherent relaxation processes in photoexcited radical-pair reactions requires tractable approaches for numerically obtaining controls for large, complex open quantum systems. Employing techniques relying on full Liouville-space propagators becomes computationally infeasible for large spin systems of realistic complexity. Here, we demonstrate how a control engineering approach based on the Pontryagin Maximum Principle (PMP) can offer a viable alternative by reporting on the successful application of PMP-optimal control to steer the coherent and incoherent spin dynamics of noisy radical pairs. This enables controls for prototypical radical-pair models that exhibit robustness in the face of relevant noise sources and paves the way to incoherent control of radical-pair spin dynamics.

The asymmetry between heating and cooling in open quantum systems is a hallmark of nonequilibrium dynamics, yet its thermodynamic origin has remained unclear. Here, we investigate the thermalization of a quantum system weakly coupled to a thermal bath, focusing on the entropy production rate and the quantum thermokinetic uncertainty relation (TKUR). We derive an analytical expression for the entropy production rate, showing that heating begins with a higher entropy production, which drives faster thermalization than cooling. The quantum TKUR links this asymmetry to heat-current fluctuations, demonstrating that larger entropy production suppresses fluctuations, making heating more stable than cooling. Our results reveal the thermodynamic basis of asymmetric thermalization and highlight uncertainty relations as key to nonequilibrium quantum dynamics.

We investigate quantum analogues of collision resistance and obtain separations between quantum “one-way” and “collision-resistant” primitives. 1. Our first result studies one-wayness versus collision-resistance defined over quantum circuits that output classical strings. We show that there is a classical oracle $\mathcal{O}$ relative to which (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a non-collapsing measurement oracle, $\mathcal{Q}^{\mathcal{O}}$. Very roughly, $\mathcal{Q}^{\mathcal{O}}$ outputs the result of multiple non-collapsing measurements on the output of any quantum $\mathcal{O}$-aided circuit. This rules out fully black-box quantum constructions of $Y$ from $X$ for any $X \in \{$indistinguishability obfuscation and one-way permutations, public-key encryption, deniable encryption, oblivious transfer, non-interactive ZK, trapdoor permutations, quantum money$\}, Y \in \{$collision-resistant hash functions, hard problems in SZK, homomorphic encryption, distributional collision-resistant puzzles$\}$. 2. Our second result studies one-wayness versus collision-resistance defined over quantum states. Here, we show that relative to the same classical oracle $\mathcal{O}$, (sub-exponentially secure) indistinguishability obfuscation and one-way permutations exist even against adversaries that make quantum queries to a cloning unitary $\mathsf{QCol}^\mathcal{O}$. Very roughly, this latter oracle implements a well-defined, linear operation to clone a subset of the qubits output by any quantum $\mathcal{O}$-aided circuit. This rules out fully black-box constructions of quantum lightning from public-key quantum money.

Controlled commands – computations whose execution depends on a separate input – play a central role in reversible Boolean circuits and quantum circuits. However, existing formalisms typically treat control only implicitly, entangled with other aspects of computation. From a semantic perspective, control is most naturally expressed in semisimple rig categories, which – unlike standard circuit models such as props – support both parallel and conditional composition. We present a construction that freely adjoins an explicit syntactic notion of control to a circuit theory specified as a suitable prop, subject to eight universally quantified equations. Our main result is that these equations are sound and complete for the intended semantics of control: the resulting theory satisfies a universal property, identifying it exactly as the circuit subtheory of the free semisimple rig completion. The proof combines coherence for rig categories with a new method based on induction over Gray codes. We illustrate the usefulness of the framework by showing that it simplifies several existing sound and complete axiomatisations of quantum circuits, isolating a small and conceptually clean set of generators and equations. In addition, the same equations yield a sound and complete axiomatisation of the multiply controlled Toffoli gate set, that is universal for reversible Boolean circuits.

One of the most fundamental problems in distribution testing is the identity testing problem: given samples $x_1,\ldots,x_s$, the goal is to determine whether the samples are drawn from a target distribution $\mathcal{D}$. When $\mathcal{D}$ is a distribution over $\bit^n$, the optimal sample complexity of identity testing is known to be $\Omega(\sqrt{2^n})$. Furthermore, most existing results assume that the samples $x_1,\ldots,x_s$ are generated independently from an unknown distribution. In this work, we overcome both of these limitations by initiating study of distribution testing in a more realistic setting. In our model, the unknown distribution is promised to be efficiently samplable, while allowing the observed samples $x_1,\ldots,x_s$ to be adversarially generated and arbitrarily correlated. Under this model, we show that polynomially many samples suffice to verify distributions. We further characterize the computational complexity of verifying classically- and quantumly-samplable distributions. Our techniques also extend to verifications of quantum states. In establishing some of our results, we employ Kolmogorov complexity techniques in a novel manner. We also present multiple applications of Kolmogorov complexity that are of independent interest. In particular, we show that certified randomness with a classical efficient prover can be achieved without computational assumptions when inefficient verification is allowed. Furthermore, we also show that a natural quantum extension of a well-studied Kolmogorov complexity measure provides a good benchmark for certifying sampling-based quantum advantage.