Efficient learning of quantum states prepared with few fermionic non-Gaussian gates

Abstract

The experimental realization of increasingly complex quantum states underscores the pressing need for new methods of state learning and verification. In one such framework, quantum state tomography, the aim is to learn the full quantum state from data obtained by measurements. Without prior assumptions on the state, this task is prohibitively hard. Here, we present an efficient algorithm for learning states on $n$ fermion modes prepared by any number of Gaussian and at most $t$ non-Gaussian gates. By Jordan-Wigner mapping, this also includes $n$-qubit states prepared by nearest-neighbour matchgate circuits with at most $t$ SWAP-gates. Our algorithm is based exclusively on single-copy measurements and produces a classical representation of a state, guaranteed to be close in trace distance to the target state. The sample and time complexity of our algorithm is $\mathrm{poly}(n,2^t)$; thus if $t=O(\log (n))$, it is efficient. We also show that, if $t$ scales slightly more than logarithmically, any learning algorithm to solve the same task must be inefficient, under common cryptographic assumptions. We also provide an efficient property testing algorithm that, given access to copies of a state, determines whether such a state is far or close to the set of states for which our learning algorithm works. In addition to the outputs of quantum circuits, our tomography algorithm is efficient for some physical target states, such as those arising in time dynamics and low-energy physics of impurity models. Beyond tomography, our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity, enabling an efficient circuit compilation method.

36 pages. Added numerical simulation, generalization to the mixed-case scenario and noise-robustness

References in corpus (41)

• Anyons in an exactly solved model and beyond
• Improved Simulation of Stabilizer Circuits
• Fermionic quantum computation
• Topological phases of fermions in one dimension
• Experimental realization of a long-range antiferromagnet in the Hubbard model with ultracold atoms
• Efficient quantum state tomography
• Fermi-Hubbard physics with atoms in an optical lattice
• Quantum Error Correction: An Introductory Guide
• Classical simulation of noninteracting-fermion quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Efficient tomography of a quantum many-body system
• Matchgates and classical simulation of quantum circuits
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Sample-optimal tomography of quantum states
• Quantum algorithms to simulate many-body physics of correlated fermions
• Fermionic partial tomography via classical shadows
• Time-Resolved Observation of Spin-Charge Deconfinement in Fermionic Hubbard Chains
• A mathematical and computational review of Hartree-Fock SCF methods in Quantum Chemistry
• Quantum Chaos is Quantum
• Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
• Fermionic Gaussian states: an introduction to numerical approaches
• Complexity of quantum impurity problems
• Matchgate Shadows for Fermionic Quantum Simulation
• Fidelity witnesses for fermionic quantum simulations
• Quantum union bounds for sequential projective measurements
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Learning t-doped stabilizer states
• Transitions in entanglement complexity in random quantum circuits by measurements
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Lower bound for the T count via unitary stabilizer nullity
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Extending matchgates into universal quantum computation
• Unscrambling Quantum Information with Clifford decoders
• Learning quantum states and unitaries of bounded gate complexity
• Bell sampling from quantum circuits
• Learning quantum many-body systems from a few copies
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• Classical simulation of non-Gaussian fermionic circuits
• Fermionic correlation functions from randomized measurements in programmable atomic quantum devices
• Hardware-Tailored Diagonalization Circuits
• Improved simulation of quantum circuits dominated by free fermionic operations

Cited by in corpus (10)

• Lie-algebraic classical simulations for quantum computing
• Learning quantum states of continuous variable systems
• The non-stabilizerness of fermionic Gaussian states
• Fermionic Magic Resources of Quantum Many-Body Systems
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Analyzing the free states of one quantum resource theory as resource states of another
• Explicit Pfaffian Formula for Amplitudes of Fermionic Gaussian Pure States in Arbitrary Pauli Bases
• PAC-learning of free-fermionic states is NP-hard
• The symplectic rank of non-Gaussian quantum states