We prove that
 NSFPAR ID:
 10212758
 Date Published:
 Journal Name:
 Quantum
 Volume:
 4
 ISSN:
 2521327X
 Page Range / eLocation ID:
 264
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 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)$ 
Classical computing plays a critical role in the advancement of quantum frontiers in the NISQ era. In this spirit, this work uses classical simulation to bootstrap Variational Quantum Algorithms (VQAs). VQAs rely upon the iterative optimization of a parameterized unitary circuit (ansatz) with respect to an objective function. Since quantum machines are noisy and expensive resources, it is imperative to classically choose the VQA ansatz initial parameters to be as close to optimal as possible to improve VQA accuracy and accelerate their convergence on today’s devices. This work tackles the problem of finding a good ansatz initialization, by proposing CAFQA, a Clifford Ansatz For Quantum Accuracy. The CAFQA ansatz is a hardwareefficient circuit built with only Clifford gates. In this ansatz, the parameters for the tunable gates are chosen by searching efficiently through the Clifford parameter space via classical simulation. The resulting initial states always equal or outperform traditional classical initialization (e.g., HartreeFock), and enable highaccuracy VQA estimations. CAFQA is wellsuited to classical computation because: a) Cliffordonly quantum circuits can be exactly simulated classically in polynomial time, and b) the discrete Clifford space is searched efficiently via Bayesian Optimization. For the Variational Quantum Eigensolver (VQE) task of molecular ground state energy estimation (up to 18 qubits), CAFQA’s Clifford Ansatz achieves a mean accuracy of nearly 99% and recovers as much as 99.99% of the molecular correlation energy that is lost in HartreeFock initialization. CAFQA achieves mean accuracy improvements of 6.4x and 56.8x, over the stateoftheart, on different metrics. The scalability of the approach allows for preliminary ground state energy estimation of the challenging chromium dimer (Cr2) molecule. With CAFQA’s highaccuracy initialization, the convergence of VQAs is shown to accelerate by 2.5x, even for small molecules. Furthermore, preliminary exploration of allowing a limited number of nonClifford (T) gates in the CAFQA framework, shows that as much as 99.9% of the correlation energy can be recovered at bond lengths for which Cliffordonly CAFQA accuracy is relatively limited, while remaining classically simulable.more » « less

Variational Quantum Algorithms (VQAs) rely upon the iterative optimization of a parameterized unitary circuit with respect to an objective function. Since quantum machines are noisy and expensive resources, it is imperative to choose a VQA's ansatz appropriately and its initial parameters to be close to optimal. This work tackles the problem of finding initial ansatz parameters by proposing CAFQA, a Clifford ansatz for quantum accuracy. The CAFQA ansatz is a hardwareefficient circuit built with only Clifford gates. In this ansatz, the initial parameters for the tunable gates are chosen by searching efficiently through the Clifford parameter space via classical simulation, thereby producing a suitable stabilizer state. The stabilizer states produced are shown to always equal or outperform traditional classical initialization (e.g., HartreeFock), and often produce high accuracy estimations prior to quantum exploration. Furthermore, the technique is classically suited since a) Clifford circuits can be exactly simulated classically in polynomial time and b) the discrete Clifford space, while scaling exponentially in the number of qubits, is searched efficiently via Bayesian Optimization. For the Variational Quantum Eigensolver (VQE) task of molecular ground state energy estimation up to 20 qubits, CAFQA's Clifford Ansatz achieves a mean accuracy of near 99%, recovering as much as 99.99% of the correlation energy over HartreeFock. Notably, the scalability of the approach allows for preliminary ground state energy estimation of the challenging Chromium dimer with an accuracy greater than HartreeFock. With CAFQA's initialization, VQA convergence is accelerated by a factor of 2.5x. In all, this work shows that stabilizer states are an accurate ansatz initialization for VQAs. Furthermore, it highlights the potential for quantuminspired classical techniques to support VQAs.more » « less

Abstract Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multiqubit control gates. In order to simulate a certain class of n qubit random Hamiltonians, we propose a drastically simplified quantum circuit that we refer to as the minimal QSVT circuit, which uses only one ancilla qubit and no multiqubit controlled gates. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. Under the globally depolarized noise model, we demonstrate that QUES is directly related to the circuit fidelity, and the potential classical hardness of an associated quantum circuit sampling problem. Under the same assumption, theoretical analysis suggests there exists an ‘optimal’ simulation time t opt ≈ 4.81, at which even a noisy quantum device may be sufficient to demonstrate the potential classical hardness.more » « less

Abstract TavisCummings (TC) cavity quantum electrodynamical effects, describing the interaction of
N atoms with an optical resonator, are at the core of atomic, optical and solid state physics. The full numerical simulation of TC dynamics scales exponentially with the number of atoms. By restricting the open quantum system to a single excitation, typical of experimental realizations in quantum optics, we analytically solve the TC model with an arbitrary number of atoms with linear complexity. This solution allows us to devise the Quantum Mapping Algorithm of Resonator Interaction withN Atoms (QMARINA), an intuitive TC mapping to a quantum circuit with linear space and time scaling, whoseN +1 qubits represent atoms and a lossy cavity, while the dynamics is encoded through 2N entangling gates. Finally, we benchmark the robustness of the algorithm on a quantum simulator and superconducting quantum processors against the quantum master equation solution on a classical computer.