Algorithms · Eigenvalue estimation
Tensor hypercontraction block encoding for quantum chemistry
Represent the spectrum of a quantum chemistry Hamiltonian, given in an arbitrary (for example molecular) orbital basis, as a block-encoded quantum circuit cheap enough to support phase estimation of a molecular eigenvalue.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Reference implementationtensor_hypercontraction
- Reported costÕ(N) Toffoli complexity for the block-encoding circuits, in a basis of N orbitals, with O(λ/ε) repetitions of those circuits needed for phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of the Hamiltonian coefficients and ε is the target precision. The abstract states this is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that up to logarithmic factors it matches the scaling of the most efficient prior block encodings restricted to an orthogonal basis.
- Papers1
This record, used inside a worked example
This page says phase estimation
— here is a concrete, runnable instance of it.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Where it ends up
- 1011100%
The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open that example in StudioRepresent the spectrum of a quantum chemistry Hamiltonian, given in an arbitrary (for example molecular) orbital basis, as a block-encoded quantum circuit cheap enough to support phase estimation of a molecular eigenvalue. Lee, Berry, Gidney, Huggins, McClean, Wiebe and Babbush describe quantum circuits that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary, for example molecular, orbitals. Their key insight is to factorize the Hamiltonian by a method the authors call tensor hypercontraction (THC), transforming the Coulomb operator into an isospectral diagonal form defined by the THC factors in a non-orthogonal basis; they then use qubitization to simulate the resulting non-orthogonal THC Hamiltonian in a way that the authors say avoids most complications of that non-orthogonal basis. The authors state that repeating these block-encoding circuits, combined with phase estimation, lets one sample in the molecular eigenbasis. They report that their construction is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that, up to logarithmic factors, it matches the scaling of the most efficient prior block encodings — ones that can work only with orthogonal basis functions diagonalizing the Coulomb operator, such as the plane wave dual basis. The authors also reanalyze and reduce the cost of several of the best prior algorithms for these simulations, to give what they describe as a clear comparison to their own construction. They report compiling their algorithm for challenging finite-sized molecules such as FeMoCo, finding it requires the least fault-tolerant resources of any known approach, and, having laid out and optimized the surface-code resources the compilation needs, report that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, under stated assumptions on cycle time and gate error rate.
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 →
Lee, Berry, Gidney, Huggins, McClean, Wiebe and Babbush describe quantum circuits that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary, for example molecular, orbitals. Their key insight is to factorize the Hamiltonian by a method the authors call tensor hypercontraction (THC), transforming the Coulomb operator into an isospectral diagonal form defined by the THC factors in a non-orthogonal basis; they then use qubitization to simulate the resulting non-orthogonal THC Hamiltonian in a way that the authors say avoids most complications of that non-orthogonal basis. The authors state that repeating these block-encoding circuits, combined with phase estimation, lets one sample in the molecular eigenbasis. They report that their construction is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that, up to logarithmic factors, it matches the scaling of the most efficient prior block encodings — ones that can work only with orthogonal basis functions diagonalizing the Coulomb operator, such as the plane wave dual basis. The authors also reanalyze and reduce the cost of several of the best prior algorithms for these simulations, to give what they describe as a clear comparison to their own construction. They report compiling their algorithm for challenging finite-sized molecules such as FeMoCo, finding it requires the least fault-tolerant resources of any known approach, and, having laid out and optimized the surface-code resources the compilation needs, report that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, under stated assumptions on cycle time and gate error rate. Reported cost: Õ(N) Toffoli complexity for the block-encoding circuits, in a basis of N orbitals, with O(λ/ε) repetitions of those circuits needed for phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of the Hamiltonian coefficients and ε is the target precision. The abstract states this is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that up to logarithmic factors it matches the scaling of the most efficient prior block encodings restricted to an orthogonal basis..
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
- tensor_hypercontraction
- Reported cost
- Õ(N) Toffoli complexity for the block-encoding circuits, in a basis of N orbitals, with O(λ/ε) repetitions of those circuits needed for phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of the Hamiltonian coefficients and ε is the target precision. The abstract states this is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that up to logarithmic factors it matches the scaling of the most efficient prior block encodings restricted to an orthogonal basis.
- Complexity basis
- The abstract of arXiv:2011.03494 states, in the raw TeX as fetched from the abs page: "We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals." Rendered into Unicode for the reader (script-O with a tilde becomes Õ, the italic N stays N), this is Õ(N) Toffoli complexity in a basis of N orbitals. The same abstract continues: "With ${\cal O}(\lambda / \epsilon)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision." — rendered here as O(λ/ε) repetitions for 1-norm λ and target precision ε. It further states "This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis." and that "up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis)" (the misspelling of Coulomb there is the abstract's own). The demonstration this record covers states no complexity bound of its own; it was read and adds nothing to this field.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Eigenvalue estimation 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: Tensor hypercontraction block encoding for quantum chemistry
PROBLEM: Represent the spectrum of a quantum chemistry Hamiltonian, given in an arbitrary (for example molecular) orbital basis, as a block-encoded quantum circuit cheap enough to support phase estimation of a molecular eigenvalue.
IDEA: Lee, Berry, Gidney, Huggins, McClean, Wiebe and Babbush describe quantum circuits that block encode the spectra of quantum chemistry Hamiltonians in a basis of N arbitrary, for example molecular, orbitals. Their key insight is to factorize the Hamiltonian by a method the authors call tensor hypercontraction (THC), transforming the Coulomb operator into an isospectral diagonal form defined by the THC factors in a non-orthogonal basis; they then use qubitization to simulate the resulting non-orthogonal THC Hamiltonian in a way that the authors say avoids most complications of that non-orthogonal basis. The authors state that repeating these block-encoding circuits, combined with phase estimation, lets one sample in the molecular eigenbasis. They report that their construction is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that, up to logarithmic factors, it matches the scaling of the most efficient prior block encodings — ones that can work only with orthogonal basis functions diagonalizing the Coulomb operator, such as the plane wave dual basis. The authors also reanalyze and reduce the cost of several of the best prior algorithms for these simulations, to give what they describe as a clear comparison to their own construction. They report compiling their algorithm for challenging finite-sized molecules such as FeMoCo, finding it requires the least fault-tolerant resources of any known approach, and, having laid out and optimized the surface-code resources the compilation needs, report that FeMoCo can be simulated using about four million physical qubits and under four days of runtime, under stated assumptions on cycle time and gate error rate.
REPORTED COST: Õ(N) Toffoli complexity for the block-encoding circuits, in a basis of N orbitals, with O(λ/ε) repetitions of those circuits needed for phase estimation to sample in the molecular eigenbasis, where λ is the 1-norm of the Hamiltonian coefficients and ε is the target precision. The abstract states this is the lowest complexity shown for quantum computations of chemistry within an arbitrary basis, and that up to logarithmic factors it matches the scaling of the most efficient prior block encodings restricted to an orthogonal basis.
BASIS: The abstract of arXiv:2011.03494 states, in the raw TeX as fetched from the abs page: "We describe quantum circuits with only $\widetilde{\cal O}(N)$ Toffoli complexity that block encode the spectra of quantum chemistry Hamiltonians in a basis of $N$ arbitrary (e.g., molecular) orbitals." Rendered into Unicode for the reader (script-O with a tilde becomes Õ, the italic N stays N), this is Õ(N) Toffoli complexity in a basis of N orbitals. The same abstract continues: "With ${\cal O}(\lambda / \epsilon)$ repetitions of these circuits one can use phase estimation to sample in the molecular eigenbasis, where $\lambda$ is the 1-norm of Hamiltonian coefficients and $\epsilon$ is the target precision." — rendered here as O(λ/ε) repetitions for 1-norm λ and target precision ε. It further states "This is the lowest complexity that has been shown for quantum computations of chemistry within an arbitrary basis." and that "up to logarithmic factors, this matches the scaling of the most efficient prior block encodings that can only work with orthogonal basis functions diagonalizing the Coloumb operator (e.g., the plane wave dual basis)" (the misspelling of Coulomb there is the abstract's own). The demonstration this record covers states no complexity bound of its own; it was read and adds nothing to this field.
PRIMARY SOURCE: Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush (2020), Even more efficient quantum computations of chemistry through tensor hypercontraction — https://arxiv.org/abs/2011.03494
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:
- Tensor hypercontraction block encoding Method
Takes An access model for — sparse-access oracles, a Pauli or LCU decomposition, a purification, or an explicit arithmetic description — plus a target precision . Returns A unitary on qubits, its subnormalization , and its ancilla/flag count . Because , Gilyén, Su, Low and Wiebe's Definition 43 forces .
Related entries
References
- Even more efficient quantum computations of chemistry through tensor hypercontraction
Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, Ryan Babbush · 2020
Primary source: it states the Õ(N) Toffoli complexity of the block-encoding circuits, the O(λ/ε) repetition count phase estimation needs to sample in the molecular eigenbasis, the tensor hypercontraction factorization and qubitization construction, and the FeMoCo compilation and surface-code resource estimate. Consult it for the derivation of the complexity bounds, the definition of λ for a specific molecule, the treatment of the non-orthogonal basis, and the reanalysis of prior algorithms' costs, none of which the abstract states in detail.