Second-quantized fermionic Hamiltonians for quantum simulation with polylogarithmic qubit and gate complexity.

William Kirby, Bryce Fuller, Charles F. Hadfield, Antonio Mezzacapo

Published Sep 29, 2021• 0 citations

Abstract

We present a method for encoding second-quantized fermionic systems in qubits when the number of fermions is conserved, as in the electronic structure problem. When the number $F$ of fermions is much smaller than the number $M$ of modes, this symmetry reduces the number of information-theoretically required qubits from $\Theta(M)$ to $O(F\log M)$. In this limit, our encoding requires $O(F^2\log^4 M)$ qubits, while encoded fermionic creation and annihilation operators have cost $O(F^2\log^5 M)$ in two-qubit gates. This is the first second-quantized encoding of fermions in qubits whose costs in qubits and gates are both polylogarithmic in $M$, which will permit studying fermionic systems in the high-precision regime of many modes.

Related papers

Succinct Fermion Data Structures

Joseph Carolan, Luke Schaeffer

arXiv:2410.04015Leibniz international proceedings in informaticsOct 5, 20241 citation

Succinct Fermion Data Structures

Carolan, Joseph, Luke Schaeffer

Jan 1, 20250 citations

Second-Quantized Fermionic Operators with Polylogarithmic Qubit and Gate Complexity

William Kirby, Bryce Fuller, Charles F. Hadfield +1 more

A new qubit encoding method for second-quantized fermion interactions in systems of relevance for quantum chemistry is described, which can achieve an exponential improvement over prior second-quantized strategies in the limit of large basis sets.

arXiv:2109.14465PRX QuantumJun 8, 202221 citations

Tapering off qubits to simulate fermionic Hamiltonians

Sergey B. Bravyi, Jay Gambetta, Antonio Mezzacapo +1 more

arXiv:1701.08213Jan 27, 2017172 citations

Optimizing qubit resources for quantum chemistry simulations in second quantization on a quantum computer

Nikolaj Moll, Andreas Fuhrer, Peter Staar +1 more

arXiv:1510.04048Journal of Physics A Mathematical and TheoreticalJun 7, 201659 citations

Optimal Fermion-Qubit Mappings via Quadratic Assignment

Mitchell Chiew, Cameron Ibrahim, Ilya Safro +1 more

arXiv:2504.21636IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20251 citation

Second-quantized fermionic Hamiltonians for quantum simulation with polylogarithmic qubit and gate complexity.

William Kirby, Bryce Fuller, Charles F. Hadfield, Antonio Mezzacapo

Published Sep 29, 2021• 0 citations

OpenAlex

Abstract

We present a method for encoding second-quantized fermionic systems in qubits when the number of fermions is conserved, as in the electronic structure problem. When the number

F

of fermions is much smaller than the number

M

of modes, this symmetry reduces the number of information-theoretically required qubits from

\Theta(M)

O(F\log M)

. In this limit, our encoding requires

O(F^2\log^4 M)

qubits, while encoded fermionic creation and annihilation operators have cost

O(F^2\log^5 M)

in two-qubit gates. This is the first second-quantized encoding of fermions in qubits whose costs in qubits and gates are both polylogarithmic in

M

, which will permit studying fermionic systems in the high-precision regime of many modes.

Related papers

Succinct Fermion Data Structures

Joseph Carolan, Luke Schaeffer

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 $\mathcal{I}:=\lceil\log \binom{M}{F}\rceil$ qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses $\mathcal I+o(\mathcal I)$ qubits when $F=o(M)$ , and allows rotations generated by creation-annihilation operators in $O(\mathcal I)$ gates and $O(\log M \log \log M)$ depth. (2) Our second construction uses $\mathcal I+O(1)$ qubits when $F=Θ(M)$ , and allows rotations generated by creation-annihilation operators in $O(\mathcal I^3)$ 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 $\mathcal{I}:=\lceil\log \binom{M}{F}\rceil$ qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses $\mathcal I+o(\mathcal I)$ qubits when $F=o(M)$, and allows rotations generated by creation-annihilation operators in $O(\mathcal I)$ gates and $O(\log M \log \log M)$ depth. (2) Our second construction uses $\mathcal I+O(1)$ qubits when $F=Θ(M)$, and allows rotations generated by creation-annihilation operators in $O(\mathcal I^3)$ 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.

arXiv:2410.04015Leibniz international proceedings in informaticsOct 5, 20241 citation

Succinct Fermion Data Structures

Carolan, Joseph, Luke Schaeffer

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.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.

Jan 1, 20250 citations

Second-Quantized Fermionic Operators with Polylogarithmic Qubit and Gate Complexity

William Kirby, Bryce Fuller, Charles F. Hadfield +1 more

arXiv:2109.14465PRX QuantumJun 8, 202221 citations

Tapering off qubits to simulate fermionic Hamiltonians

Sergey B. Bravyi, Jay Gambetta, Antonio Mezzacapo +1 more

We discuss encodings of fermionic many-body systems by qubits in the presence of symmetries. Such encodings eliminate redundant degrees of freedom in a way that preserves a simple structure of the system Hamiltonian enabling quantum simulations with fewer qubits. First we consider $U(1)$ symmetry describing the particle number conservation. Using a previously known encoding based on the first quantization method a system of $M$ fermi modes with $N$ particles can be simulated on a quantum computer with $Q=N\log{(M)}$ qubits. We propose a new version of this encoding tailored to variational quantum algorithms. Also we show how to improve sparsity of the simulator Hamiltonian using orthogonal arrays. Next we consider encodings based on the second quantization method. It is shown that encodings with a given filling fraction $ν=N/M$ and a qubit-per-mode ratio $η=Q/M<1$ can be constructed from efficiently decodable classical LDPC codes with the relative distance $2ν$ and the encoding rate $1-η$ . A family of codes based on high-girth bipartite graphs is discussed. Graph-based encodings eliminate roughly $M/N$ qubits. Finally we consider discrete symmetries, and show how to eliminate qubits using previously known encodings, illustrating the technique for simple molecular-type Hamiltonians.We discuss encodings of fermionic many-body systems by qubits in the presence of symmetries. Such encodings eliminate redundant degrees of freedom in a way that preserves a simple structure of the system Hamiltonian enabling quantum simulations with fewer qubits. First we consider $U(1)$ symmetry describing the particle number conservation. Using a previously known encoding based on the first quantization method a system of $M$ fermi modes with $N$ particles can be simulated on a quantum computer with $Q=N\log{(M)}$ qubits. We propose a new version of this encoding tailored to variational quantum algorithms. Also we show how to improve sparsity of the simulator Hamiltonian using orthogonal arrays. Next we consider encodings based on the second quantization method. It is shown that encodings with a given filling fraction $ν=N/M$ and a qubit-per-mode ratio $η=Q/M<1$ can be constructed from efficiently decodable classical LDPC codes with the relative distance $2ν$ and the encoding rate $1-η$. A family of codes based on high-girth bipartite graphs is discussed. Graph-based encodings eliminate roughly $M/N$ qubits. Finally we consider discrete symmetries, and show how to eliminate qubits using previously known encodings, illustrating the technique for simple molecular-type Hamiltonians.

arXiv:1701.08213Jan 27, 2017172 citations

Optimizing qubit resources for quantum chemistry simulations in second quantization on a quantum computer

Nikolaj Moll, Andreas Fuhrer, Peter Staar +1 more

Abstract Quantum chemistry simulations on a quantum computer suffer from the overhead needed for encoding the Fermionic problem in a system of qubits. By exploiting the block diagonality of a Fermionic Hamiltonian, we show that the number of required qubits can be reduced while the number of terms in the Hamiltonian will increase. All operations for this reduction can be performed in operator space. The scheme is conceived as a pre-computational step that would be performed prior to the actual quantum simulation. We apply this scheme to reduce the number of qubits necessary to simulate both the Hamiltonian of the two-site Fermi–Hubbard model and the hydrogen molecule. Both quantum systems can then be simulated with a two-qubit quantum computer. Despite the increase in the number of Hamiltonian terms, the scheme still remains a useful tool to reduce the dimensionality of specific quantum systems for quantum simulators with a limited number of resources.Abstract Quantum chemistry simulations on a quantum computer suffer from the overhead needed for encoding the Fermionic problem in a system of qubits. By exploiting the block diagonality of a Fermionic Hamiltonian, we show that the number of required qubits can be reduced while the number of terms in the Hamiltonian will increase. All operations for this reduction can be performed in operator space. The scheme is conceived as a pre-computational step that would be performed prior to the actual quantum simulation. We apply this scheme to reduce the number of qubits necessary to simulate both the Hamiltonian of the two-site Fermi–Hubbard model and the hydrogen molecule. Both quantum systems can then be simulated with a two-qubit quantum computer. Despite the increase in the number of Hamiltonian terms, the scheme still remains a useful tool to reduce the dimensionality of specific quantum systems for quantum simulators with a limited number of resources.

arXiv:1510.04048Journal of Physics A Mathematical and TheoreticalJun 7, 201659 citations

Optimal Fermion-Qubit Mappings via Quadratic Assignment

Mitchell Chiew, Cameron Ibrahim, Ilya Safro +1 more

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_QubitAssignmentSimulation 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

arXiv:2504.21636IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20251 citation

We present a method for encoding second-quantized fermionic systems in qubits when the number of fermions is conserved, as in the electronic structure problem. When the number

F

of fermions is much smaller than the number

M

of modes, this symmetry reduces the number of information-theoretically required qubits from

\Theta(M)

O(F\log M)

. In this limit, our encoding requires

O(F^2\log^4 M)

qubits, while encoded fermionic creation and annihilation operators have cost

O(F^2\log^5 M)

in two-qubit gates. This is the first second-quantized encoding of fermions in qubits whose costs in qubits and gates are both polylogarithmic in

M

, which will permit studying fermionic systems in the high-precision regime of many modes.

F

fermions in

M

modes. An information theoretic minimum of

\mathcal{I}:=\lceil\log \binom{M}{F}\rceil

qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses

\mathcal I+o(\mathcal I)

qubits when

F=o(M)

, and allows rotations generated by creation-annihilation operators in

O(\mathcal I)

gates and

O(\log M \log \log M)

depth. (2) Our second construction uses

\mathcal I+O(1)

qubits when

F=Θ(M)

, and allows rotations generated by creation-annihilation operators in

O(\mathcal I^3)

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.

U(1)

symmetry describing the particle number conservation. Using a previously known encoding based on the first quantization method a system of

M

fermi modes with

N

particles can be simulated on a quantum computer with

Q=N\log{(M)}

qubits. We propose a new version of this encoding tailored to variational quantum algorithms. Also we show how to improve sparsity of the simulator Hamiltonian using orthogonal arrays. Next we consider encodings based on the second quantization method. It is shown that encodings with a given filling fraction

ν=N/M

and a qubit-per-mode ratio

η=Q/M<1

can be constructed from efficiently decodable classical LDPC codes with the relative distance

2ν

and the encoding rate

1-η

. A family of codes based on high-girth bipartite graphs is discussed. Graph-based encodings eliminate roughly

M/N

qubits. Finally we consider discrete symmetries, and show how to eliminate qubits using previously known encodings, illustrating the technique for simple molecular-type Hamiltonians.