Abstract “Classical shadows” are estimators of an unknown quantum state, constructed from suitably distributed random measurements on copies of that state (Huang et al. in Nat Phys 16:1050, 2020, https://doi.org/10.1038/s41567-020-0932-7 ). In this paper, we analyze classical shadows obtained using random matchgate circuits, which correspond to fermionic Gaussian unitaries. We prove that the first three moments of the Haar distribution over the continuous group of matchgate circuits are equal to those of the discrete uniform distribution over only the matchgate circuits that are also Clifford unitaries; thus, the latter forms a “matchgate 3-design.” This implies that the classical shadows resulting from the two ensembles are functionally equivalent. We show how one can use these matchgate shadows to efficiently estimate inner products between an arbitrary quantum state and fermionic Gaussian states, as well as the expectation values of local fermionic operators and various other quantities, thus surpassing the capabilities of prior work. As a concrete application, this enables us to apply wavefunction constraints that control the fermion sign problem in the quantum-classical auxiliary-field quantum Monte Carlo algorithm (QC-AFQMC) (Huggins et al. in Nature 603:416, 2022, https://doi.org/10.1038/s41586-021-04351-z ), without the exponential post-processing cost incurred by the original approach.
Abstract “Classical shadows” are estimators of an unknown quantum state, constructed from suitably distributed random measurements on copies of that state (Huang et al. in Nat Phys 16:1050, 2020, https://doi.org/10.1038/s41567-020-0932-7 ). In this paper, we analyze classical shadows obtained using random matchgate circuits, which correspond to fermionic Gaussian unitaries. We prove that the first three moments of the Haar distribution over the continuous group of matchgate circuits are equal to those of the discrete uniform distribution over only the matchgate circuits that are also Clifford unitaries; thus, the latter forms a “matchgate 3-design.” This implies that the classical shadows resulting from the two ensembles are functionally equivalent. We show how one can use these matchgate shadows to efficiently estimate inner products between an arbitrary quantum state and fermionic Gaussian states, as well as the expectation values of local fermionic operators and various other quantities, thus surpassing the capabilities of prior work. As a concrete application, this enables us to apply wavefunction constraints that control the fermion sign problem in the quantum-classical auxiliary-field quantum Monte Carlo algorithm (QC-AFQMC) (Huggins et al. in Nature 603:416, 2022, https://doi.org/10.1038/s41586-021-04351-z ), without the exponential post-processing cost incurred by the original approach.
Abstract Estimating quantum fermionic properties is a computationally difficult yet crucial task for the study of electronic systems. Recent developments have begun to address this challenge by introducing classical shadows protocols relying on sampling of Fermionic Gaussian Unitaries (FGUs): a class of transformations in fermionic space which can be conveniently mapped to matchgates circuits. The different protocols proposed in the literature use different sub-ensembles of the orthogonal group O(2n) to which FGUs can be associated. We propose an approach that unifies these different protocols, proving their equivalence, and deriving from it an optimal sampling scheme. We begin by demonstrating that the first three moments of the FGU ensemble associated with SO(2n) and of its intersection with the Clifford group are equal, generalizing a result known for O(2n) and addressing a question raised in previous works. Building on this proof, we establish the equivalence between the shadows protocols resulting from FGU ensembles analyzed in the literature. Finally, from our results, we propose a sampling scheme for a small sub-ensemble of matchgates circuits that is optimal in terms of number of gates and that inherits the performances guarantees of the previous ensembles.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.
Solving the electronic structure problem of molecules and solids to high accuracy is a major challenge in quantum chemistry and condensed matter physics. The rapid emergence and development of quantum computers offer a promising route to systematically tackle this problem. Recent work by [Huggins , ] proposed a hybrid quantum-classical quantum Monte Carlo (QC-QMC) algorithm using Clifford shadows to determine the ground state of a Fermionic Hamiltonian. This approach displayed inherent noise resilience and the potential for improved accuracy compared to its purely classical counterpart. Nevertheless, the use of Clifford shadows introduces an exponentially scaling postprocessing cost. In this work, we investigate an improved QC-QMC scheme utilizing the recently developed Matchgate shadows technique [], which removes the aforementioned exponential bottleneck. We observe from experiments on quantum hardware that the use of Matchgate shadows in QC-QMC is inherently noise robust. We show that this noise resilience has a more subtle origin than in the case of Clifford shadows. Nevertheless, we find that classical postprocessing, while asymptotically efficient, requires hours of runtime on thousands of classical CPUs for even the smallest chemical systems, presenting a major challenge to the scalability of the algorithm. Published by the American Physical Society 2024
High Resolution Image Download MS PowerPoint Slide Quantum Monte Carlo (QMC) methods are powerful approaches for solving electronic structure problems. Although they often provide high-accuracy solutions, the precision of most QMC methods is ultimately limited by the trial wave function that must be used. Recently, an approach has been demonstrated to allow the use of trial wave functions prepared on a quantum computer [Huggins et al., Unbiasing fermionic quantum Monte Carlo with a quantum computer. Nature 2022, 603, 416] in the auxiliary-field QMC (AFQMC) method using classical shadows to estimate the required overlaps. However, this approach has an exponential post-processing step to construct these overlaps when performing classical shadows obtained using random Clifford circuits. Here, we study an approach to avoid this exponential scaling step by using a fixed-node Monte Carlo method based on full configuration interaction quantum Monte Carlo. This method is applied to the local unitary cluster Jastrow ansatz. We consider H 4, ferrocene, and benzene molecules using up to 12 qubits as examples. Circuits are compiled to native gates for typical near-term architectures, and we assess the impact of circuit-level depolarizing noise on the method. We also provide a comparison of AFQMC and fixed-node approaches, demonstrating that AFQMC is more robust to errors, although extrapolations of the fixed-node energy reduce this discrepancy. Although the method can be used to reach chemical accuracy, the sampling cost to achieve this is high even for small active spaces, suggesting caution about the prospect of outperforming conventional QMC approaches.
Fermionic Gaussian states (FGSs) and the associated matchgate circuits play a central role in quantum information theory and condensed matter physics. Despite being possibly highly entangled, they can still be efficiently simulated on classical computers. We address the question of how to optimally create such states when using matchgate circuits acting on product states. To this end, we derive lower bounds on the number of gates required to prepare an arbitrary pure FGS: We establish both an asymptotic bound on the minimal gate count over general nearest-neighbor gate sets and an exact bound for circuits composed solely of matchgates. We present explicit algorithms whose constructions saturate these bounds, thereby proving their optimality. We furthermore determine when an FGS can be prepared with a circuit of any given depth, and derive an algorithm that constructs such a circuit whenever this condition is satisfied, either exactly or approximately. Our results have direct applications to (approximate) state preparation and to disentangling procedures. Moreover, we introduce a new classical simulation algorithm for matchgate circuits, based entirely on manipulating the generating circuits of the FGSs. Finally, we briefly study an extension of our framework for t-doped Gaussian states and circuits.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T gate (a T unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between n-qubit matchgate circuits and the standard representation of SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n) incurred in this smaller-dimensional representation translates at most into an O(nεSO(2n)) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XX Hamiltonian on n=4,8 qubits.