The classical shadows protocol, recently introduced by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)], is a quantum-classical protocol to estimate properties of an unknown quantum state. Unlike full quantum state tomography, the protocol can be implemented on near-term quantum hardware and requires few quantum measurements to make many predictions with a high success probability. In this paper, we study the effects of noise on the classical shadows protocol. In particular, we consider the scenario in which the quantum circuits involved in the protocol are subject to various known noise channels and derive an analytical upper bound for the sample complexity in terms of a shadow seminorm for both local and global noise. Additionally, by modifying the classical post-processing step of the noiseless protocol, we define a new estimator that remains unbiased in the presence of noise. As applications, we show that our results can be used to prove rigorous sample complexity upper bounds in the cases of depolarizing noise and amplitude damping.

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (PH) does not collapse, a stronger version of the statement thatP≠NP, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH(a) and per-int-NSETH(b) take specific classical counting problems related to the number of zeros of a degree-3 polynomial innvariables overF2or the permanent of ann×ninteger-valued matrix, and assert that any non-deterministic algorithm that solves them requires2cntime steps, wherec∈{a,b}. A third conjecture poly3-ave-SBSETH(a′) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity classSBP. We analyze evidence for these conjectures and argue that they are plausible whena=1/2,b=0.999anda′=1/2.Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring104to107gates.

The number of measurements demanded by hybrid quantum-classical algorithms such as the variational quantum eigensolver (VQE) is prohibitively high for many problems of practical value. For such problems, realizing quantum advantage will require methods that dramatically reduce this cost. Previous quantum algorithms that reduce the measurement cost (e.g., quantum amplitude and phase estimation) require error rates that are too low for near-term implementation. Here we propose methods that take advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing the measurement number and runtime compared to the standard sampling method of the VQE. Our scheme derives inspiration from quantum metrology, phase estimation, and the more recent “alpha-VQE” proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits. The central object of this method is what we call the “engineered likelihood function” (ELF), used for carrying out Bayesian inference. We show how the ELF formalism enhances the rate of information gain in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers to that of quantum error–corrected ones. This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond. Similar to the VQE, we expect small-scale implementations to be realizable on today’s quantum devices.

Classical shadows provide a noise-resilient and sample-efficient method for learning quantum system properties, relying on a user-specified unitary ensemble. What is the weakest assumption on this ensemble that can still yield meaningful results? To address this, we focus on Pauli-invariant unitary ensembles—those invariant under multiplication by Pauli operators. For these ensembles, we present explicit formulas for the reconstruction map and sample complexity bounds and extend our results to the case when noise impacts the protocol implementation. Two applications are explored: one for locally scrambled unitary ensembles, where we present formulas for the reconstruction map and sample complexity bounds that circumvent the need to solve an exponential-sized linear system, and another for the classical shadows of quantum channels. Our results establish a unified framework for classical shadows with Pauli-invariant unitary ensembles, applicable to both noisy and noiseless scenarios for states and channels and primed for implementation on near-term quantum devices.

In theoretical machine learning, the statistical complexity is a notion that measures the richness of a hypothesis space. In this work, we apply a particular measure of statistical complexity, namely, the Rademacher complexity, to the quantum circuit model in quantum computation and study how the statistical complexity depends on various quantum circuit parameters. In particular, we investigate the dependence of the statistical complexity on the resources, depth, width, and the number of input and output registers of a quantum circuit. To study how the statistical complexity scales with resources in the circuit, we introduce a magic resource measure based on the $(p,q)$ group norm, which quantifies the amount of magic resource in the quantum channels associated with the circuit. These dependencies are investigated in the following two settings: (i) where the entire quantum circuit is treated as a single quantum channel, and (ii) where each layer of the quantum circuit is treated as a separate quantum channel. The bounds we obtain can be used to constrain the capacity of quantum neural networks in terms of their depths and widths as well as the resources in the network.

With the advent of quantum information, the violation of a Bell inequality is used to witness the absence of an eavesdropper in cryptographic scenarios such as key distribution and randomness expansion. One of the key assumptions of Bell’s theorem is the existence of experimental “free will,” meaning that measurement settings can be chosen at random and independently by each party. The relaxation of this assumption potentially shifts the balance of power towards an eavesdropper. We consider a no-signaling model with reduced “free will” and bound the adversary’s capabilities in the task of randomness expansion.