Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States.

We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states. First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the l_{1} norm, of a large fraction of Clifford circuits. The running time of our algorithm decreases as the inputs become more mixed. Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured. This restriction depends on a magic monotone that we call the Pauli rank. We apply our results to give an efficient output probability approximation algorithm for some restricted quantum computation models, such as Clifford circuits with solely magic state inputs, Pauli-based computation, and instantaneous quantum polynomial time circuits. Finally, we discuss the relationship between Pauli rank and stabilizer rank.

Effects of reduced measurement independence on Bell-based randomness expansion.

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.

Variational quantum evolution equation solver.

Variational quantum algorithms offer a promising new paradigm for solving partial differential equations on near-term quantum computers. Here, we propose a variational quantum algorithm for solving a general evolution equation through implicit time-stepping of the Laplacian operator. The use of encoded source states informed by preceding solution vectors results in faster convergence compared to random re-initialization. Through statevector simulations of the heat equation, we demonstrate how the time complexity of our algorithm scales with the Ansatz volume for gradient estimation and how the time-to-solution scales with the diffusion parameter. Our proposed algorithm extends economically to higher-order time-stepping schemes, such as the Crank-Nicolson method. We present a semi-implicit scheme for solving systems of evolution equations with non-linear terms, such as the reaction-diffusion and the incompressible Navier-Stokes equations, and demonstrate its validity by proof-of-concept results.