Algorithms · Hamiltonian simulation · model systems
Quantum algorithms to simulate many-body physics of correlated fermions
Simulate strongly correlated fermionic systems — notoriously hard for classical computers — on a quantum computer with 2D or linear (1D) nearest-neighbor qubit-qubit couplings, of the kind typical of superconducting transmon qubit arrays, including preparing the relevant quantum states and evolving the system in time, with the Fermi-Hubbard model as a worked example.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Reference implementationfermi_hubbard_model_1D
- Reported costThree separate bounds, each attached to the subroutine the abstract attaches it to, not merged into one figure for the algorithm as a whole: preparing an arbitrary fermionic Gaussian state costs O(N²) gates and O(N) circuit depth; the 2D fermionic Fourier transform on a 2D qubit array costs O(N^1.5) gates and O(√N) circuit depth, described as the minimum depth needed for quantum information to cross the array; and simulating each time step of the 2D Fermi-Hubbard model, again on a 2D qubit array, costs O(N) gates and O(√N) circuit depth. None of the three is a total cost for a full simulation, and none is stated by the abstract specifically for the one-dimensional (linear) geometry this record's reference implementation demonstrates: the abstract names linear geometry as within its scope but attaches no gate or depth bound to it.
- Papers1
Simulate strongly correlated fermionic systems — notoriously hard for classical computers — on a quantum computer with 2D or linear (1D) nearest-neighbor qubit-qubit couplings, of the kind typical of superconducting transmon qubit arrays, including preparing the relevant quantum states and evolving the system in time, with the Fermi-Hubbard model as a worked example. Jiang, Sung, Kechedzhi, Smelyanskiy and Boixo discuss quantum simulation of strongly correlated fermionic systems, following Feynman's proposal to use a quantum computer for a problem notoriously hard on classical ones, and focus specifically on 2D and linear geometry with nearest-neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays. They improve an existing algorithm for preparing an arbitrary Slater determinant by exploiting a unitary symmetry, and present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with O(N²) gates and O(N) circuit depth; both algorithms, the authors say, are optimal in that the number of parameters in the circuit equals the number needed to describe the state. They also propose an algorithm for the 2D fermionic Fourier transform on a 2D qubit array with O(N^1.5) gates and O(√N) circuit depth, which they identify as the minimum depth required for quantum information to travel across the array. Separately, they present methods to simulate each time step of the evolution of the 2D Fermi-Hubbard model, again on a 2D qubit array, with O(N) gates and O(√N) circuit depth. The authors close by discussing how these algorithms can be used to determine the ground-state properties and phase diagrams of strongly correlated quantum systems, with the Hubbard model as their example.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Jiang, Sung, Kechedzhi, Smelyanskiy and Boixo discuss quantum simulation of strongly correlated fermionic systems, following Feynman's proposal to use a quantum computer for a problem notoriously hard on classical ones, and focus specifically on 2D and linear geometry with nearest-neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays. They improve an existing algorithm for preparing an arbitrary Slater determinant by exploiting a unitary symmetry, and present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with O(N²) gates and O(N) circuit depth; both algorithms, the authors say, are optimal in that the number of parameters in the circuit equals the number needed to describe the state. They also propose an algorithm for the 2D fermionic Fourier transform on a 2D qubit array with O(N^1.5) gates and O(√N) circuit depth, which they identify as the minimum depth required for quantum information to travel across the array. Separately, they present methods to simulate each time step of the evolution of the 2D Fermi-Hubbard model, again on a 2D qubit array, with O(N) gates and O(√N) circuit depth. The authors close by discussing how these algorithms can be used to determine the ground-state properties and phase diagrams of strongly correlated quantum systems, with the Hubbard model as their example. Reported cost: Three separate bounds, each attached to the subroutine the abstract attaches it to, not merged into one figure for the algorithm as a whole: preparing an arbitrary fermionic Gaussian state costs O(N²) gates and O(N) circuit depth; the 2D fermionic Fourier transform on a 2D qubit array costs O(N^1.5) gates and O(√N) circuit depth, described as the minimum depth needed for quantum information to cross the array; and simulating each time step of the 2D Fermi-Hubbard model, again on a 2D qubit array, costs O(N) gates and O(√N) circuit depth. None of the three is a total cost for a full simulation, and none is stated by the abstract specifically for the one-dimensional (linear) geometry this record's reference implementation demonstrates: the abstract names linear geometry as within its scope but attaches no gate or depth bound to it..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Reference implementation
- fermi_hubbard_model_1D
- Reported cost
- Three separate bounds, each attached to the subroutine the abstract attaches it to, not merged into one figure for the algorithm as a whole: preparing an arbitrary fermionic Gaussian state costs O(N²) gates and O(N) circuit depth; the 2D fermionic Fourier transform on a 2D qubit array costs O(N^1.5) gates and O(√N) circuit depth, described as the minimum depth needed for quantum information to cross the array; and simulating each time step of the 2D Fermi-Hubbard model, again on a 2D qubit array, costs O(N) gates and O(√N) circuit depth. None of the three is a total cost for a full simulation, and none is stated by the abstract specifically for the one-dimensional (linear) geometry this record's reference implementation demonstrates: the abstract names linear geometry as within its scope but attaches no gate or depth bound to it.
- Complexity basis
- The abstract of arXiv:1711.05395 states three separate gate-count and depth bounds, each attached by the abstract itself to a different subroutine; this record keeps them attached to those subroutines rather than folding them into one figure for the whole algorithm. On Gaussian state preparation: "We also present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with $O(N^2)$ gates and $O(N)$ circuit depth." On the 2D fermionic Fourier transform: "we propose an algorithm to implement the 2-dimensional (2D) fermionic Fourier transformation on a 2D qubit array with only $O(N^{1.5})$ gates and" — the abstract then gives the depth bound in TeX using a square root, rendered here as O(√N) since it is written outside quotation marks — and resumes: "circuit depth, which is the minimum depth required for quantum information to travel across the qubit array." On the Fermi-Hubbard time step: "We also present methods to simulate each time step in the evolution of the 2D Fermi-Hubbard model---again on a 2D qubit array---with $O(N)$ gates and" — again a TeX square-root depth bound, rendered O(√N) outside quotes — before: "circuit depth." All three bounds are stated for a 2D qubit array. The same abstract separately states, "We focus specifically on 2D and linear geometry with nearest neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays." That sentence puts linear (one-dimensional) geometry within the paper's scope but attaches no gate or depth bound to it anywhere in the abstract. This record's reference implementation demonstrates the one-dimensional case, so none of the three quoted bounds is claimed here to describe it. The demonstration gives no bound of its own.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Hamiltonian simulation · model systems with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Quantum algorithms to simulate many-body physics of correlated fermions
PROBLEM: Simulate strongly correlated fermionic systems — notoriously hard for classical computers — on a quantum computer with 2D or linear (1D) nearest-neighbor qubit-qubit couplings, of the kind typical of superconducting transmon qubit arrays, including preparing the relevant quantum states and evolving the system in time, with the Fermi-Hubbard model as a worked example.
IDEA: Jiang, Sung, Kechedzhi, Smelyanskiy and Boixo discuss quantum simulation of strongly correlated fermionic systems, following Feynman's proposal to use a quantum computer for a problem notoriously hard on classical ones, and focus specifically on 2D and linear geometry with nearest-neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays. They improve an existing algorithm for preparing an arbitrary Slater determinant by exploiting a unitary symmetry, and present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with O(N²) gates and O(N) circuit depth; both algorithms, the authors say, are optimal in that the number of parameters in the circuit equals the number needed to describe the state. They also propose an algorithm for the 2D fermionic Fourier transform on a 2D qubit array with O(N^1.5) gates and O(√N) circuit depth, which they identify as the minimum depth required for quantum information to travel across the array. Separately, they present methods to simulate each time step of the evolution of the 2D Fermi-Hubbard model, again on a 2D qubit array, with O(N) gates and O(√N) circuit depth. The authors close by discussing how these algorithms can be used to determine the ground-state properties and phase diagrams of strongly correlated quantum systems, with the Hubbard model as their example.
REPORTED COST: Three separate bounds, each attached to the subroutine the abstract attaches it to, not merged into one figure for the algorithm as a whole: preparing an arbitrary fermionic Gaussian state costs O(N²) gates and O(N) circuit depth; the 2D fermionic Fourier transform on a 2D qubit array costs O(N^1.5) gates and O(√N) circuit depth, described as the minimum depth needed for quantum information to cross the array; and simulating each time step of the 2D Fermi-Hubbard model, again on a 2D qubit array, costs O(N) gates and O(√N) circuit depth. None of the three is a total cost for a full simulation, and none is stated by the abstract specifically for the one-dimensional (linear) geometry this record's reference implementation demonstrates: the abstract names linear geometry as within its scope but attaches no gate or depth bound to it.
BASIS: The abstract of arXiv:1711.05395 states three separate gate-count and depth bounds, each attached by the abstract itself to a different subroutine; this record keeps them attached to those subroutines rather than folding them into one figure for the whole algorithm. On Gaussian state preparation: "We also present a quantum algorithm to prepare an arbitrary fermionic Gaussian state with $O(N^2)$ gates and $O(N)$ circuit depth." On the 2D fermionic Fourier transform: "we propose an algorithm to implement the 2-dimensional (2D) fermionic Fourier transformation on a 2D qubit array with only $O(N^{1.5})$ gates and" — the abstract then gives the depth bound in TeX using a square root, rendered here as O(√N) since it is written outside quotation marks — and resumes: "circuit depth, which is the minimum depth required for quantum information to travel across the qubit array." On the Fermi-Hubbard time step: "We also present methods to simulate each time step in the evolution of the 2D Fermi-Hubbard model---again on a 2D qubit array---with $O(N)$ gates and" — again a TeX square-root depth bound, rendered O(√N) outside quotes — before: "circuit depth." All three bounds are stated for a 2D qubit array. The same abstract separately states, "We focus specifically on 2D and linear geometry with nearest neighbor qubit-qubit couplings, typical for superconducting transmon qubit arrays." That sentence puts linear (one-dimensional) geometry within the paper's scope but attaches no gate or depth bound to it anywhere in the abstract. This record's reference implementation demonstrates the one-dimensional case, so none of the three quoted bounds is claimed here to describe it. The demonstration gives no bound of its own.
PRIMARY SOURCE: Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi, Vadim N. Smelyanskiy, Sergio Boixo (2017), Quantum algorithms to simulate many-body physics of correlated fermions — https://arxiv.org/abs/1711.05395
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Where this sits
This record is named by the layer graph at:
- Simulate Hamiltonian evolution Slot
Takes An access model for — a sum of efficiently exponentiable terms, sparse-access oracles, or a block-encoding — plus an evolution time and a target error . Returns A circuit approximating to within , with a stated query or gate count, an ancilla count, and the norm parameter — sparsity times , or the LCU 1-norm — that the cost is measured against.
Related entries
- Fermi–Hubbard Hamiltonian
Operators
- Fermi-Hubbard dimer operator (Jordan-Wigner encoded)
Operators
- Trotter–Suzuki Hamiltonian simulation
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Quantum algorithms to simulate many-body physics of correlated fermions
Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi, Vadim N. Smelyanskiy, Sergio Boixo · 2017
Primary source: it presents three separate subroutines with the gate-count and circuit-depth bounds quoted above — fermionic Gaussian state preparation, the 2D fermionic Fourier transform, and one time step of 2D Fermi-Hubbard evolution — an improved Slater-determinant preparation algorithm, and a discussion of using these algorithms for ground-state properties and phase diagrams via the Hubbard model. Consult it for what happens in the one-dimensional (linear) geometry the abstract names but does not bound, for the meaning of N, and for the Slater-determinant improvement, none of which the abstract itself gives beyond what is quoted here.