The efficient encoding of the fermionic Schrödinger equation as a spin system Hamiltonian is a long-term problem. I describe an encoding for the fermionic position space Schrödinger equation on a finite-volume periodic lattice with a local potential. The challenging part of the construction is the implementation of the kinetic energy operator, which is essentially the Laplacian. The finite difference implementation on the lattice combines contributions from neighboring lattice sites, which is complicated by fermionic exchange symmetry. Two independently useful techniques developed here are operator filtering and entanglement gadgets. Operator filtering is useful when a simple operator acting on a subspace of the full Hilbert space has a desired set of interactions. Occupation suppression of the complement of the subspace then filters away unwanted contributions of the operator. Entanglement gadgets encode the same information differently in two sets of qubits. We may then independently choose the most efficient encoding for operators acting on the qubits. The construction for the Laplacian described here has $\mathcal{O}\left(An 2^D\right)$ cost in bounded Pauli weight terms where $A$ is the number of identical spinless fermions, $N=2^n$ is the number of lattice points in each direction, and $D$ is the number of dimensions. The finite volume context protects the gap between the ground state and the first excited state, yielding polynomial time complexity with the box size.
The efficient encoding of the fermionic Schrödinger equation as a spin system Hamiltonian is a long-term problem. I describe an encoding for the fermionic position space Schrödinger equation on a finite-volume periodic lattice with a local potential. The challenging part of the construction is the implementation of the kinetic energy operator, which is essentially the Laplacian. The finite difference implementation on the lattice combines contributions from neighboring lattice sites, which is complicated by fermionic exchange symmetry. Two independently useful techniques developed here are operator filtering and entanglement gadgets. Operator filtering is useful when a simple operator acting on a subspace of the full Hilbert space has a desired set of interactions. Occupation suppression of the complement of the subspace then filters away unwanted contributions of the operator. Entanglement gadgets encode the same information differently in two sets of qubits. We may then independently choose the most efficient encoding for operators acting on the qubits. The construction for the Laplacian described here has O(An2D) cost in bounded Pauli weight terms where A is the number of identical spinless fermions, N=2n is the number of lattice points in each direction, and D is the number of dimensions. The finite volume context protects the gap between the ground state and the first excited state, yielding polynomial time complexity with the box size.
Simulating electronic structure on a quantum computer requires encoding of fermionic systems onto qubits. Common encoding methods transform a fermionic system of N spin-orbitals into an N-qubit system, but many of the fermionic configurations do not respect the required conditions and symmetries of the system so the qubit Hilbert space in this case may have unphysical states and thus cannot be fully utilized. We propose a generalized qubit-efficient encoding (QEE) scheme that requires the qubit number to be only logarithmic in the number of configurations that satisfy the required conditions and symmetries. For the case of considering only the particle-conserving and singlet configurations, we reduce the qubit count to an upper bound of O(mlog2N), where m is the number of particles. This QEE scheme is demonstrated on an H2 molecule in the 6-31G basis set and a LiH molecule in the STO-3G basis set using fewer qubits than the common encoding methods. We calculate the ground-state energy surfaces using a variational quantum eigensolver algorithm with a hardware-efficient ansatz circuit. We choose to use a hardware-efficient ansatz since most of the Hilbert space in our scheme is spanned by desired configurations so a heuristic search for an eigenstate is sensible. The simulations are performed on IBM Quantum machines and the Qiskit simulator with a noise model implemented from a IBM Quantum machine. Using the methods of measurement error mitigation and error-free linear extrapolation, we demonstrate that most of the distributions of the extrapolated energies using our QEE scheme agree with the exact results obtained by Hamiltonian diagonalization in the given basis sets within chemical accuracy. Our proposed scheme and results show the feasibility of quantum simulations for larger molecular systems in the noisy intermediate-scale quantum (NISQ) era. The number of terms in the Hamiltonian has an upper bound of $\mathcal{O}(\frac{{N}^{2m+1}}{(m\ensuremath{-}1)!\phantom{\rule{0.16em}{0ex}}m!})$ for the QEE scheme while it scales as O(N4) for the Jordan-Wigner encoding scheme. Nevertheless, we present several cases where QEE is useful.
Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of F fermions in M modes. An information theoretic minimum of I:=⌈log(FM)⌉ qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses I+o(I) qubits when F=o(M), and allows rotations generated by creation-annihilation operators in O(I) gates and O(logMloglogM) depth. (2) Our second construction uses I+O(1) qubits when F=Θ(M), and allows rotations generated by creation-annihilation operators in O(I3) gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes.
Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of F fermions in M modes. An information theoretic minimum of I: = ⌈log₂ binom(M,F)⌉ qubits is required for such systems, a bound we nearly match over the entire parameter regime. 1) Our first construction uses I + o(I) qubits when F = o(M), and allows rotations generated by creation-annihilation operators in O(I) gates and O(log M log log M) depth. 2) Our second construction uses I + O(1) qubits when F = Θ(M), and allows rotations generated by creation-annihilation operators in O(I³) gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes.
A compelling application of quantum computers with thousands of qubits is quantum simulation. Simulating fermionic systems is both a problem with clear real-world applications and a computationally challenging task. In order to simulate a system of fermions on a quantum computer, one has to first map the fermionic Hamiltonian to a qubit Hamiltonian. The most popular such mapping is the Jordan-Wigner encoding, which suffers from inefficiencies caused by the high weight of some encoded operators. As a result, alternative local encodings have been proposed that solve this problem at the expense of a constant factor increase in the number of qubits required. Some such encodings possess local stabilizers, i.e., Pauli operators that act as the logical identity on the encoded fermionic modes. A natural error mitigation approach in these cases is to measure the stabilizers and discard any run where a measurement returns a -1 outcome. Using a high-performance stabilizer simulator, we classically simulate the performance of a local encoding known as the Derby-Klassen encoding and compare its performance with the Jordan-Wigner encoding and the ternary tree encoding. Our simulations use more complex error models and significantly larger system sizes (up to 18×18) than in previous work. We find that the high sampling requirements of postselection methods with the Derby-Klassen encoding pose a limitation to its applicability in near-term devices and call for more encoding-specific circuit optimizations.
A Complete Proof of QMA1-Hardness for Weighted Gapped Clique Homology
The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be QMA1-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed a reduction intended to establish the same hardness result in this setting.
We give a complete proof of the hard direction. The earlier King-Kohler argument contains a gap in the analysis of the nontrivially folded local gadgets, so the required topological and spectral properties have to be re-established on the clique complexes actually produced by the reduction. This is not a local repair of the published proof: the argument requires a new analysis of the local topology, the filtered cochain complexes, and the interaction of many overlapping gadgets.
Our proof uses exact finite certificates for the local combinatorial data and relative homology to determine the effect of each gadget on the encoded qubit space. We then prove the finite-dimensional filtered-Hodge statement needed to recover the corresponding rank-one low-energy penalty and derive a quantitative global estimate that transfers the source-Hamiltonian promise gap to the final weighted Hodge Laplacian. Consequently, for fixed efficiently computable k(n) and inverse-polynomial γ(n), weighted gapped clique homology is QMA1(G)-hard. The previously known QMA-containment argument is logically independent of the gap and remains unaffected.
Motivated by recent progress of quantum technologies making small-scale programmable quantum computing possible, here we study a discretized quantum adiabatic process for a one-dimensional free-fermion system described by a variational wave function, i.e., a parametrized quantum circuit.The wave function is composed of M layers of two elementary sets of time-evolution operators, each set being decomposed into commutable local operators acting on neighboring sites.The evolution time of each time-evolution operator is treated as a variational parameter so as to minimize the expectation value of the energy.We show that the exact ground state is reached by applying the layers of time-evolution operators as many as a quarter of the system size, implying that at least in this case, the state is exactly prepared in a quantum circuit with linear depth.This is the minimum number M B of layers set by the limit of speed, i.e., the Lieb-Robinson bound, for propagating quantum entanglement via the local time-evolution operators.Indeed, we show the mutual information of the variational wave function that reveals a causality-cone-like structure in the propagation of quantum entanglement.Quantities such as the energy E and the entanglement entropy S of the optimized variational wave function with the number M of layers less than M B are independent of the system size L but fall into some universal functions of M, indicating that the entanglement generated in this variational ansatz with a finite M is bounded, as in the case of the matrix product states with a finite bond dimension.Furthermore, in this case, we find that these two quantities behave asymptotically as E /L -ε ∞ ∼ M -2 (ε ∞ : the exact ground-state energy per site in the thermodynamic limit) and S ≈ 1 3 ln M. The development of the entanglement in the variational ansatz through the discretized quantum adiabatic process is further manifested in the progressive propagation of single-particle orbitals in the variational wave function.We also find that the optimized variational parameters converge systematically to a smooth function of the discretized time, which provides the optimum scheduling function in the quantum adiabatic process, with the effective total evolution time of the variational ansatz to the exact ground state being proportional to the system size L.This is a drastic improvement compared to the evolution time proportional to L 2 for the continuous-time quantum adiabatic process with a linear scheduling and is attributed to diabaticity of the discretized quantum adiabatic process represented in the variational ansatz.Finally, we investigate the imaginary-time evolution counterpart of this variational wave function, where the causality relation is absent due to the nonunitarity of the imaginary-time evolution operators, and thus the norm of the wave function is no longer conserved.We find that the convergence to the exact ground state is exponentially fast, despite that the system is at the critical point, suggesting that implementation of the nonunitary imaginary-time evolution in a quantum circuit is highly promising to further shallow the circuit depth, provided that the local nonunitary operators are represented with a reasonable amount of unitary operators.