paper / barbaraterhal / Oct 2
This paper investigates the optimization problem for fermionic Hamiltonians with classical interactions, which is QMA-hard due to its connection to Coulomb electron-electron interaction. The authors demonstrate that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for these Hamiltonians, irrespective of sparsity. This finding indicates that classical interactions successfully prevent the vanishing Gaussian approximation ratio observed in SYK-type models. The work also presents efficient semi-definite programming algorithms for Gaussian approximations.
quantum-physicsfermionic-hamiltoniansclassical-interactionsqma-hardgaussian-statesquantum-chemistrycondensed-matter
“The optimization problem for fermionic Hamiltonians with classical interactions is QMA-hard.”
paper / barbaraterhal / May 19
Transversal logical gates in the surface code enable fast, low-noise quantum logic, but interspersing them with parity check measurements creates complex, cross-gate decoding challenges. This work presents a "logical observable" minimum-weight-perfect-matching (MWPM) decoder capable of handling arbitrary sequences of transversal gates on the unrotated surface code under circuit-level noise. Two windowed decoder variants are introduced: a computationally efficient basic decoder suited for slow (quiescent) resets, and an advanced two-step decoder supporting fast resets at the cost of computational efficiency. Both decoders expose sublinear-in-d error structures that can cause logical failures, and the authors propose targeted adaptations to eliminate them.
quantum-error-correctionsurface-codeclifford-gatesquantum-decodingfault-tolerant-quantum-computingminimum-weight-perfect-matchinglogical-gates
“A logical observable MWPM-based decoder can decode across an arbitrary sequence of transversal Clifford gates for the unrotated surface code under circuit-level noise.”
paper / barbaraterhal / Dec 9
Fermionic k-SAT, a quantum generalization of classical SAT, is introduced to determine if a fermionic state exists in the null-space of parity-conserving projectors. Importantly, Fermionic 2-SAT is shown to be classically solvable, even with fixed particle number parity constraints. However, introducing a specific particle number constraint for Fermionic 2-SAT escalates its complexity to NP-complete, and Fermionic 9-SAT is proven to be QMA1-hard.
fermionic-systemsquantum-satisfiabilitycomputational-complexityquantum-algorithmsnp-completenessqma-hardness
“Fermionic 2-SAT, a problem determining if a fermionic state exists in the null-space of specific projectors, can be solved efficiently using classical computation.”
paper / barbaraterhal / Sep 6
A novel quantum algorithm drastically improves the simulation of noninteracting fermion systems, offering exponential memory and runtime advantages over classical methods for certain geometries. This advancement is critical for addressing computational bottlenecks in large-scale many-body physics problems, particularly those involving disordered, inhomogeneous, or large non-lattice graphical structures. The technique of block-encoding key mathematical objects into quantum unitaries underpins these performance gains.
quantum-computingquantum-algorithmsfermion-systemscomputational-physicsquantum-simulationbqp-complexity
“Quantum algorithms can solve free-fermion problems with significantly reduced computational costs compared to classical methods.”
paper / barbaraterhal / Jul 23
This paper introduces generalized morphing circuits to reduce the qubit connectivity requirements for Bivariate Bicycle (BB) codes from six to five, while maintaining their numerical performance. The authors also present a framework for designing these circuits and demonstrate the potential for logical input/output with an ancillary surface code in a biplanar layout. This advancement provides a method for improving the practical implementation of BB codes in quantum error correction.
quantum-computing-architecturequantum-error-correctionbivariate-bicycle-codesmorphing-circuitsqubit-connectivityquantum-information-theory
“Bivariate Bicycle (BB) codes can achieve similar logical performance to surface codes but with an improved encoding rate.”