Algorithms · Diagonalization · double-bracket flow
Double-bracket iterations for diagonalization
Find quantum circuits that diagonalize a given input Hamiltonian, that is, approximate its eigenstates, without resorting to brute-force optimization of an unstructured variational circuit, which runs into barren plateaus.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Unknown
- Primary source on the speedupNot stated by the primary source — arXiv:2206.11772 as retrieved — the abstract, the full introduction, sections 1.1 to 1.3, sections 1.6 and 1.7 where the query recursion is derived, part of section 2.2, Proposition 5 in section 3, section 4 on open questions, and fragments of the appendices. Every comparison in that text is against other quantum approaches — brute-force variational circuit optimization and quantum phase estimation — and the classical Lanczos algorithm appears only as context for a different paper's quantum adaptation, never as a baseline for this algorithm's cost. Section 2's numerical examples, section 5 and most of the appendix proofs were not retrieved and were not read. was read and makes no such claim
- Reported costExponential in the number of recursion steps, and stated as such by the paper about its own method. The query count to the evolution oracle satisfies N(k+1) = 3N(k) + 1, whose solution with N(1) = 1 gives at most (3 + o(1))^K queries for K group-commutator recursion steps.
- Papers1
Find quantum circuits that diagonalize a given input Hamiltonian, that is, approximate its eigenstates, without resorting to brute-force optimization of an unstructured variational circuit, which runs into barren plateaus. The method is a recursion in which each step conjugates the current Hamiltonian by the exponential of a commutator between it and a diagonal operator, the diagonal operator and the step duration both being chosen variationally. Each step is realized on a quantum computer by a group-commutator construction built purely from queries to an oblivious evolution oracle and from diagonal Clifford evolutions, so the abstract can say that no qubit overheads or controlled-unitary operations are needed. A transpiling algorithm assembles the query list recursively for a chosen number of steps. The paper's framing is that this replaces unstructured optimization with a structured flow that does not suffer the same trainability limitations, at an implementation cost lower than quantum phase estimation requires.
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 →
The method is a recursion in which each step conjugates the current Hamiltonian by the exponential of a commutator between it and a diagonal operator, the diagonal operator and the step duration both being chosen variationally. Each step is realized on a quantum computer by a group-commutator construction built purely from queries to an oblivious evolution oracle and from diagonal Clifford evolutions, so the abstract can say that no qubit overheads or controlled-unitary operations are needed. A transpiling algorithm assembles the query list recursively for a chosen number of steps. The paper's framing is that this replaces unstructured optimization with a structured flow that does not suffer the same trainability limitations, at an implementation cost lower than quantum phase estimation requires. This record's speedup class, "Unknown", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Not stated by the primary source — arXiv:2206.11772 as retrieved — the abstract, the full introduction, sections 1.1 to 1.3, sections 1.6 and 1.7 where the query recursion is derived, part of section 2.2, Proposition 5 in section 3, section 4 on open questions, and fragments of the appendices. Every comparison in that text is against other quantum approaches — brute-force variational circuit optimization and quantum phase estimation — and the classical Lanczos algorithm appears only as context for a different paper's quantum adaptation, never as a baseline for this algorithm's cost. Section 2's numerical examples, section 5 and most of the appendix proofs were not retrieved and were not read. was read and makes no such claim. Reported cost: Exponential in the number of recursion steps, and stated as such by the paper about its own method. The query count to the evolution oracle satisfies N(k+1) = 3N(k) + 1, whose solution with N(1) = 1 gives at most (3 + o(1))^K queries for K group-commutator recursion steps..
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
- Speedup class (secondary source)
- Unknown
- Primary source on the speedup
- Not stated by the primary source — arXiv:2206.11772 as retrieved — the abstract, the full introduction, sections 1.1 to 1.3, sections 1.6 and 1.7 where the query recursion is derived, part of section 2.2, Proposition 5 in section 3, section 4 on open questions, and fragments of the appendices. Every comparison in that text is against other quantum approaches — brute-force variational circuit optimization and quantum phase estimation — and the classical Lanczos algorithm appears only as context for a different paper's quantum adaptation, never as a baseline for this algorithm's cost. Section 2's numerical examples, section 5 and most of the appendix proofs were not retrieved and were not read. was read and makes no such claim
- Reported cost
- Exponential in the number of recursion steps, and stated as such by the paper about its own method. The query count to the evolution oracle satisfies N(k+1) = 3N(k) + 1, whose solution with N(1) = 1 gives at most (3 + o(1))^K queries for K group-commutator recursion steps.
- Speedup class
- Unknown (checked against the record's own primary paper, which does not state it)
- Complexity basis
- abstract of arXiv:2206.11772: "the method is recursive which makes the circuit depth grow exponentially with the number of recursion steps."; sections 1.6 and 1.7, equations 51-52: "N (k + 1) = 3N (k) + 1 . The solution of this recursion, with N(1) = 1 as the starting point, gives the final result of queries to the evolution oracle to perform K GCI recursion steps N(K) ≤ (3 + o(1))^K , so an exponential scaling in the number of steps."; the introduction states the same: "The recursive character of double-bracket iterations leads to an exponential runtime of the quantum algorithms in the number of iteration steps."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Diagonalization · double-bracket flow 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: Double-bracket iterations for diagonalization
PROBLEM: Find quantum circuits that diagonalize a given input Hamiltonian, that is, approximate its eigenstates, without resorting to brute-force optimization of an unstructured variational circuit, which runs into barren plateaus.
IDEA: The method is a recursion in which each step conjugates the current Hamiltonian by the exponential of a commutator between it and a diagonal operator, the diagonal operator and the step duration both being chosen variationally. Each step is realized on a quantum computer by a group-commutator construction built purely from queries to an oblivious evolution oracle and from diagonal Clifford evolutions, so the abstract can say that no qubit overheads or controlled-unitary operations are needed. A transpiling algorithm assembles the query list recursively for a chosen number of steps. The paper's framing is that this replaces unstructured optimization with a structured flow that does not suffer the same trainability limitations, at an implementation cost lower than quantum phase estimation requires.
REPORTED COST: Exponential in the number of recursion steps, and stated as such by the paper about its own method. The query count to the evolution oracle satisfies N(k+1) = 3N(k) + 1, whose solution with N(1) = 1 gives at most (3 + o(1))^K queries for K group-commutator recursion steps.
BASIS: abstract of arXiv:2206.11772: "the method is recursive which makes the circuit depth grow exponentially with the number of recursion steps."; sections 1.6 and 1.7, equations 51-52: "N (k + 1) = 3N (k) + 1 . The solution of this recursion, with N(1) = 1 as the starting point, gives the final result of queries to the evolution oracle to perform K GCI recursion steps N(K) ≤ (3 + o(1))^K , so an exponential scaling in the number of steps."; the introduction states the same: "The recursive character of double-bracket iterations leads to an exponential runtime of the quantum algorithms in the number of iteration steps."
PRIMARY SOURCE: Marek Gluza (2022), Double-bracket quantum algorithms for diagonalization — https://arxiv.org/abs/2206.11772
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:
- Estimate a Hamiltonian's ground-state energy Slot
Takes A Hermitian reachable as a sum of terms, as sparse-access oracles or as a block-encoding; a way to prepare trial states, and — for the methods that need it — a trial state whose overlap with the ground state is not negligible; a target additive error and a confidence . Returns A scalar estimate of the lowest eigenvalue with a stated additive-error guarantee, plus the run or query budget it consumed. Whether that estimate is also a rigorous upper bound is a property of the method and is not promised by the slot.
Related entries
- Quantum imaginary-time evolution
Algorithms
- Variational quantum eigensolver for ground-state energy
Algorithms
- Quantum phase estimation
Algorithms
References
- Double-bracket quantum algorithms for diagonalization
Marek Gluza · 2022
Primary source, and the source of this record's cost claim. Consult it for the group-commutator construction that realizes one step from evolution-oracle queries alone, for the recursion in sections 1.6 and 1.7 that makes the query count exponential in the number of steps, and for section 4, where the author states there is no runtime guarantee for the variational version that would actually be run.