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.
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.
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.
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.
Classical shadows (CS) has recently emerged as an important framework to efficiently predict properties of an unknown quantum state. A common strategy in CS protocols is to parametrize the basis in which one measures the state by a random group action; many examples of this have been proposed and studied on a case-by-case basis. In this work, we present a unified theory that allows us to simultaneously understand CS protocols based on sampling from general group representations, extending previous approaches that worked in simplified (multiplicity-free) settings. We identify a class of measurement bases which we call "centralizing bases" that allows us to analytically characterize and invert the measurement channel, minimizing classical post-processing costs. We complement this analysis by deriving general bounds on the sample-complexity necessary to obtain estimates of a given precision. Beyond its unification of previous CS protocols, our method allows us to readily generate new protocols based on other groups, or different representations of previously considered ones. For example, we characterize novel shadow protocols based on sampling from the spin and tensor representations of SU(2), symmetric and orthogonal groups, and the exceptional Lie group G2.
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of 2n Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an n-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in O(n2) time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to n=80 qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements ×2.57 and ×2.28 in the total number of gates, respectively.