Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the p
olynomial hierarchy that approximating the output probabilities of random quantum circuits to within $exp(-Omega(mlog m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is $#mathsf{P}$-hard under $mathsf{BPP}^{mathsf{NP}}$ reduction. In the recent experiments, the quantum circuit has $n$-qubits and the architecture is a two-dimensional grid of size $sqrt{n}timessqrt{n}$. Indeed for constant depth circuits approximating the output probabilities to within $2^{-Omega(nlog{n})}$ is hard. For circuits of depth $log{n}$ or $sqrt{n}$ for which the anti-concentration property holds, approximating the output probabilities to within $2^{-Omega(nlog^2{n})}$ and $2^{-Omega(n^{3/2}log n)}$ is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturis lemma, and Rakhmanovs result.
We introduce a framework for constructing a quantum error correcting code from any classical error correcting code. This includes CSS codes and goes beyond the stabilizer formalism to allow quantum codes to be constructed from classical codes that ar
e not necessarily linear or self-orthogonal (Fig. 1). We give an algorithm that explicitly constructs quantum codes with linear distance and constant rate from classical codes with a linear distance and rate. As illustrations for small size codes, we obtain Steanes $7-$qubit code uniquely from Hammings [7,4,3] code, and obtain other error detecting quantum codes from other explicit classical codes of length 4 and 6. Motivated by quantum LDPC codes and the use of physics to protect quantum information, we introduce a new 2-local frustration free quantum spin chain Hamiltonian whose ground space we analytically characterize completely. By mapping classical codewords to basis states of the ground space, we utilize our framework to demonstrate that the ground space contains explicit quantum codes with linear distance. This side-steps the Bravyi-Terhal no-go theorem because our work allows for more general quantum codes beyond the stabilizer and/or linear codes. We hesitate to call this an example of {it subspace} quantum LDPC code with linear distance.
The generic behavior of quantum systems has long been of theoretical and practical interest. Any quantum process is represented by a sequence of quantum channels. Random channels appear in a wide variety of applications, from quantum chaos to hologra
phic dualities in theories of quantum gravity to operator dynamics, to random local circuits for their potential to demonstrate quantum supremacy. We consider general ergodic sequences of stochastic channels with arbitrary correlations and non-negligible decoherence. Ergodicity includes and vastly generalizes random independence. We obtain a theorem which shows that the composition of such a sequence of channels converges exponentially fast to a rank-one (entanglement breaking) channel. Using this, we derive the limiting behavior of translation invariant channels, and stochastically independent random channels. We then use our formalism to describe the thermodynamic limit of ergodic Matrix Product States. We derive formulas for the expectation value of a local observable and prove that the 2-point correlations of local observables decay exponentially. We then analytically compute the entanglement spectrum across any cut, by which the bipartite entanglement entropy (i.e., R{e}nyi or von Neumann) across an arbitrary cut can be computed exactly. Other physical implications of our results are that most Floquet phases of matter are meta-stable, and that noisy random circuits in the large depth limit will be trivial as far as their quantum entanglement is concerned. To obtain these results we bridge quantum information theory to dynamical systems and random matrix theory.
Detection and manipulation of excitations with non-Abelian statistics, such as Majorana fermions, are essential for creating topological quantum computers. To this end, we show the connection between the existence of such localized particles and the
phenomenon of unitary subharmonic response (SR) in periodically driven systems. In particular, starting from highly nonequilibrium initial states, the unpaired Majorana modes exhibit spin oscillations with twice the driving period, are localized, and can have exponentially long lifetimes in clean systems. While the lifetime of SR is limited in translationally invariant systems, we show that disorder can be engineered to stabilize the subharmonic response of Majorana modes. A viable observation of this phenomenon can be achieved using modern multiqubit hardware, such as superconducting circuits and cold atomic systems.
Any quantum process is represented by a sequence of quantum channels. We consider ergodic processes, obtained by sampling channel valued random variables along the trajectories of an ergodic dynamical system. Examples of such processes include the ef
fect of repeated application of a fixed quantum channel perturbed by arbitrary correlated noise, or a sequence of channels drawn independently and identically from an ensemble. Under natural irreducibility conditions, we obtain a theorem showing that the state of a system evolving by such a process converges exponentially fast to an ergodic sequence of states depending on the process, but independent of the initial state of the system. As an application, we describe the thermodynamic limit of ergodic matrix product states and prove that the 2-point correlations of local observables in such states decay exponentially with their distance in the bulk. Further applications and physical implications of our results are discussed in the companion paper [11].
We consider the task of estimating the expectation value of an $n$-qubit tensor product observable $O_1otimes O_2otimes cdots otimes O_n$ in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms f
or optimization, machine learning, and the simulation of quantum many-body systems. Here we study its computational complexity for constant-depth quantum circuits and three types of single-qubit observables $O_j$ which are (a) close to the identity, (b) positive semidefinite, (c) arbitrary. It is shown that the mean value problem admits a classical approximation algorithm with runtime scaling as $mathrm{poly}(n)$ and $2^{tilde{O}(sqrt{n})}$ in cases (a,b) respectively. In case (c) we give a linear-time algorithm for geometrically local circuits on a two-dimensional grid. The mean value is approximated with a small relative error in case (a), while in cases (b,c) we satisfy a less demanding additive error bound. The algorithms are based on (respectively) Barvinoks polynomial interpolation method, a polynomial approximation for the OR function arising from quantum query complexity, and a Monte Carlo method combined with Matrix Product State techniques. We also prove a technical lemma characterizing a zero-free region for certain polynomials associated with a quantum circuit, which may be of independent interest.
As Moores law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be bey
ond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a $53-$qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard ($#P$-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.
One-parameter interpolations between any two unitary matrices (e.g., quantum gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path $U(theta)$ obt
ained from the QR-factorization [ U(theta)R(theta)=(1-theta)A+theta B, ] where $U_1 R_1=A$ and $U_2 R_2=B$ are the QR-factorizations of $A$ and $B$, and $U(theta)$ is a unitary for all $theta$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to, instead of $U(theta)$, output a matrix whose columns are proportional to the corresponding columns of $U(theta)$ and whose entries are polynomial or rational functions of $theta$. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to $theta$. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is $#P$-Hard on average, which is a simpler alternative to Bouland et als. (Dis)Proving the quantum supremacy conjecture requires approximate average case hardness; this remains an open problem for all quantum supremacy proposals.
In this paper, we explore quantum interference in molecular conductance from the point of view of graph theory and walks on lattices. By virtue of the Cayley-Hamilton theorem for characteristic polynomials and the Coulson-Rushbrooke pairing theorem f
or alternant hydrocarbons, it is possible to derive a finite series expansion of the Greens function for electron transmission in terms of the odd powers of the vertex adjacency matrix or H{u}ckel matrix. This means that only odd-length walks on a molecular graph contribute to the conductivity through a molecule. Thus, if there are only even-length walks between two atoms, quantum interference is expected to occur in the electron transport between them. However, even if there are only odd-length walks between two atoms, a situation may come about where the contributions to the QI of some odd-length walks are canceled by others, leading to another class of quantum interference. For non-alternant hydrocarbons, the finite Greens function expansion may include both even and odd powers. Nevertheless, QI can in some circumstances come about for non-alternants, from the cancellation of odd and even-length walk terms. We report some progress, but not a complete resolution of the problem of understanding the coefficients in the expansion of the Greens function in a power series of the adjacency matrix, these coefficients being behind the cancellations that we have mentioned. And we introduce a perturbation theory for transmission as well as some potentially useful infinite power series expansions of the Greens function.
In recent experiments, time-dependent periodic fields are used to create exotic topological phases of matter with potential applications ranging from quantum transport to quantum computing. These nonequilibrium states, at high driving frequencies, ex
hibit the quintessential robustness against local disorder similar to equilibrium topological phases. However, proving the existence of such topological phases in a general setting is an open problem. We propose a universal effective theory that leverages on modern free probability theory and ideas in random matrices to analytically predict the existence of the topological phase for finite driving frequencies and across a range of disorder. We find that, depending on the strength of disorder, such systems may be topological or trivial and that there is a transition between the two. In particular, the theory predicts the critical point for the transition between the two phases and provides the critical exponents. We corroborate our results by comparing them to exact diagonalizations for driven-disordered 1D Kitaev chain and 2D Bernevig-Hughes-Zhang models and find excellent agreement. This Letter may guide the experimental efforts for exploring topological phases.
