Quantum Simulation of Electronic Structure with Linear Depth and Connectivity

As physical implementations of quantum architectures emerge, it is increasingly important to consider the cost of algorithms for practical connectivities between qubits. We show that by using an arrangement of gates that we term the fermionic swap network, we can simulate a Trotter step of the electronic structure Hamiltonian in exactly $N$ depth and with $N^2/2$ two-qubit entangling gates, and prepare arbitrary Slater determinants in at most $N/2$ depth, all assuming only a minimal, linearly connected architecture. We conjecture that no explicit Trotter step of the electronic structure Hamiltonian is possible with fewer entangling gates, even with arbitrary connectivities. These results represent significant practical improvements on the cost of most Trotter-based algorithms for both variational and phase-estimation-based simulation of quantum chemistry.

Figure 1

A depiction of how the canonical Jordan-Wigner ordering changes throughout five layers of fermionic swap gates. Each circle represents a qubit in a linear array (qubits do not move) and ${\phi }_p$ labels which spin-orbital occupancy is encoded by the qubit during a particular gate layer. The lines in between qubits indicate fermionic swap gates which change the canonical ordering so that the spin orbitals are represented by different qubits in the subsequent layer. After $N$ layers, the canonical ordering is reversed, and each spin orbital has been adjacent to all others exactly once.

Figure 2

The numbers above indicate the order in which matrix elements should be eliminated using nearest-neighbor Givens rotations. We see that two elements must be eliminated before any parallelization can begin. Each element is eliminated via rotation with the row directly above it. We place asterisks (*) on the upper diagonal to emphasize that one only needs to focus on removing the lower-diagonal elements; since the initial matrix and rotations are both unitary, the upper diagonals will be eliminated simultaneously.