Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.
Simulation of fermionic systems is one of the most promising applications of quantum computers. It spans problems in quantum chemistry, high-energy physics and condensed matter. Underpinning the core steps of any quantum simulation algorithm, fermion-qubit mappings translate the fermionic interactions to the operators and states of quantum computers. This translation is highly non-trivial: a burgeoning supply of fermion-qubit mappings has arisen over the past twenty years to address the limited resources of early quantum technology. Previous literature has presented a dichotomy between ancillafree fermion-qubit mappings, which minimise qubit count, and local encodings, which minimise gate complexity. We present two computational approaches to the construction of general mappings while working with a limited number of qubits, striking a balance between the low-qubit and low-gate demands of present quantum technology. The first method frames the order of fermionic labels as an instance of the quadratic assignment problem to minimize the total and maximum Pauli weights in a problem Hamiltonian. We compare the orderoptimized performance of several common ancilla-free mappings on systems of size up to 225 fermionic modes. The second method is a computational approach to incrementally add ancilla qubits to Jordan-Wigner transformations and further reduce the Pauli weights. By adding up to 10 ancilla qubits, we were able to reduce the total Pauli weight by as much as 67 % in JordanWigner transformations of fermionic systems with up to 64 modes, outperforming the previous state-of-the-art ancilla-free mappings. Reproducibility: source code and data are available at https://github.com/cameton/QCE_QubitAssignment
Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.
Digital quantum simulation of fermionic systems is important in the context of chemistry and physics. Simulating fermionic models on general purpose quantum computers requires imposing a fermionic algebra on qubits. The previously studied Jordan-Wigner and Bravyi-Kitaev transformations are two techniques for accomplishing this task. Here, we reexamine an auxiliary fermion construction which maps fermionic operators to local operators on qubits. The local simulation is performed by relaxing the requirement that the number of qubits should match the number of single-particle states. Instead, auxiliary sites are introduced to enable nonconsecutive fermionic couplings to be simulated with constant low-rank tensor products on qubits. The additional number of auxiliary qubits required per fermionic degree of freedom depends only on the degree of connectivity of the Hamiltonian. We connect the auxiliary fermion construction to topological models and give examples of the construction.
Quantum simulation of fermionic systems is a promising application of quantum computers, but to program them, we need to map fermionic states and operators to qubit states and quantum gates. While quantum processors may be built as two-dimensional qubit networks with couplings between nearest neighbors, standard fermion-to-qubit mappings do not account for that kind of connectivity. In this work we concatenate the (one-dimensional) Jordan-Wigner transform with specific quantum codes defined under the addition of a certain number of auxiliary qubits. This yields a class of mappings with which any fermionic system can be embedded in a two-dimensional qubit setup, fostering scalable quantum simulation. Our technique is demonstrated on the two-dimensional Fermi-Hubbard model, which we transform into a local Hamiltonian. What is more, we adapt the Verstraete-Cirac transform and Bravyi-Kitaev superfast simulation to the square lattice connectivity and compare them to our mappings. An advantage of our approach in this comparison is that it allows us to encode and decode a logical state with a simple unitary quantum circuit.
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.