How fast a state of a system converges to a stationary state is one of the fundamental questions in science. Some Markov chains and random walks on finite groups are known to exhibit the nonasymptotic convergence to a stationary distribution, called the cutoff phenomenon. Here, we examine how quickly a random quantum circuit could transform a quantum state to a Haarmeasure random quantum state. We find that random quantum states, as stationary states of random walks on a unitary group, are invariant under the quantum Fourier transform (QFT). Thus the entropic uncertainty of random quantum states has balanced Shannon entropies for the computational basis and the QFT basis. By calculating the Shannon entropy for random quantum states and the Wasserstein distances for the eigenvalues of random quantum circuits, we show that the cutoff phenomenon occurs for the random quantum circuit. It is also demonstrated that the DysonBrownian motion for the eigenvalues of a random unitary matrix as a continuous random walk exhibits the cutoff phenomenon. The results here imply that random quantum states could be generated with shallow random circuits.
more » « less NSFPAR ID:
 10452895
 Publisher / Repository:
 IOP Publishing
 Date Published:
 Journal Name:
 Electronic Structure
 Volume:
 5
 Issue:
 3
 ISSN:
 25161075
 Page Range / eLocation ID:
 Article No. 035004
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haarrandom twoqubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.more » « less

Abstract Variational hybrid quantumclassical algorithms (VHQCAs) are nearterm algorithms that leverage classical optimization to minimize a cost function, which is efficiently evaluated on a quantum computer. Recently VHQCAs have been proposed for quantum compiling, where a target unitary
U is compiled into a shortdepth gate sequenceV . In this work, we report on a surprising form of noise resilience for these algorithms. Namely, we find one often learns the correct gate sequenceV (i.e. the correct variational parameters) despite various sources of incoherent noise acting during the costevaluation circuit. Our main results are rigorous theorems stating that the optimal variational parameters are unaffected by a broad class of noise models, such as measurement noise, gate noise, and Pauli channel noise. Furthermore, our numerical implementations on IBM’s noisy simulator demonstrate resilience when compiling the quantum Fourier transform, Toffoli gate, and Wstate preparation. Hence, variational quantum compiling, due to its robustness, could be practically useful for noisy intermediatescale quantum devices. Finally, we speculate that this noise resilience may be a general phenomenon that applies to other VHQCAs such as the variational quantum eigensolver. 
Abstract We prove that
depth local random quantum circuits with two qudit nearestneighbor gates on a$${{\,\textrm{poly}\,}}(t) \cdot n^{1/D}$$ $\phantom{\rule{0ex}{0ex}}\text{poly}\phantom{\rule{0ex}{0ex}}\left(t\right)\xb7{n}^{1/D}$D dimensional lattice withn qudits are approximatet designs in various measures. These include the “monomial” measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was due to Brandão–Harrow–Horodecki (Commun Math Phys 346(2):397–434, 2016) for$${{\,\textrm{poly}\,}}(t)\cdot n$$ $\phantom{\rule{0ex}{0ex}}\text{poly}\phantom{\rule{0ex}{0ex}}\left(t\right)\xb7n$ . We also improve the “scrambling” and “decoupling” bounds for spatially local random circuits due to Brown and Fawzi (Scrambling speed of random quantum circuits, 2012). One consequence of our result is that assuming the polynomial hierarchy ($$D=1$$ $D=1$ ) is infinite and that certain counting problems are$${{\,\mathrm{\textsf{PH}}\,}}$$ $\phantom{\rule{0ex}{0ex}}\mathrm{PH}\phantom{\rule{0ex}{0ex}}$ hard “on average”, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constantdepth quantum circuits was known to be hard for classical computers under these assumptions. However the standard strategy for extending this hardness result to approximate sampling requires the quantum circuits to have a property called “anticoncentration”, meaning roughly that the output has nearmaximal entropy. Unitary 2designs have the desired anticoncentration property. Our result improves the required depth for this level of anticoncentration from linear depth to a sublinear value, depending on the geometry of the interactions. This is relevant to a recent experiment by the Google Quantum AI group to perform such a sampling task with 53 qubits on a twodimensional lattice (Arute in Nature 574(7779):505–510, 2019; Boixo et al. in Nate Phys 14(6):595–600, 2018) (and related experiments by USTC), and confirms their conjecture that$$\#{\textsf{P}}$$ $\#P$ depth suffices for anticoncentration. The proof is based on a previous construction of$$O(\sqrt{n})$$ $O\left(\sqrt{n}\right)$t designs by Brandão et al. (2016), an analysis of how approximate designs behave under composition, and an extension of the quasiorthogonality of permutation operators developed by Brandão et al. (2016). Different versions of the approximate design condition correspond to different norms, and part of our contribution is to introduce the norm corresponding to anticoncentration and to establish equivalence between these various norms for lowdepth circuits. For random circuits with longrange gates, we use different methods to show that anticoncentration happens at circuit size corresponding to depth$$O(n\ln ^2 n)$$ $O\left(n{ln}^{2}n\right)$ . We also show a lower bound of$$O(\ln ^3 n)$$ $O\left({ln}^{3}n\right)$ for the size of such circuit in this case. We also prove that anticoncentration is possible in depth$$\Omega (n \ln n)$$ $\Omega (nlnn)$ (size$$O(\ln n \ln \ln n)$$ $O(lnnlnlnn)$ ) using a different model.$$O(n \ln n \ln \ln n)$$ $O(nlnnlnlnn)$ 
Abstract The quantum walk formalism is a widely used and highly successful framework for modeling quantum systems, such as simulations of the Dirac equation, different dynamics in both the low and high energy regime, and for developing a wide range of quantum algorithms. Here we present the circuitbased implementation of a discretetime quantum walk in position space on a fivequbit trappedion quantum processor. We encode the space of walker positions in particular multiqubit states and program the system to operate with different quantum walk parameters, experimentally realizing a Dirac cellular automaton with tunable mass parameter. The quantum walk circuits and position state mapping scale favorably to a larger model and physical systems, allowing the implementation of any algorithm based on discretetime quantum walks algorithm and the dynamics associated with the discretized version of the Dirac equation.

We explore how to build quantum circuits that compute the lowest energy state corresponding to a given Hamiltonian within a symmetry subspace by explicitly encoding it into the circuit. We create an explicit unitary and a variationally trained unitary that maps any vector output by ansatz A(α→) from a defined subspace to a vector in the symmetry space. The parameters are trained varitionally to minimize the energy, thus keeping the output within the labelled symmetry value. The method was tested for a spin XXZ Hamiltonian using rotation and reflection symmetry and H2 Hamiltonian within Sz=0 subspace using S2 symmetry. We have found the variationally trained unitary gives good results with very low depth circuits and can thus be used to prepare symmetry states within near term quantum computers.more » « less