Algorithms · Quantum Fourier transform
Matrix elements of irreducible group representations
Estimate a matrix element of a unitary irreducible representation of a group — a single entry of a matrix whose dimension may be exponentially large — to within an additive error, for the symmetric and alternating groups and for the unitary, special unitary and special orthogonal groups of polynomial highest weight.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
QFT then its inverse, on |0101⟩
4 qubits, starting at |0101⟩, applying the QFT then immediately undoing it.
Step 1 of 4 · X
Probability of each outcome after this step
- 0100100%
Prepares qubit 2 as |1⟩.
The whole state moves from 0000 to 0100 — one certain outcome before, one certain outcome after, no superposition either side.
Prepares qubit 0 as |1⟩, so the register reads |0101⟩.
The whole state moves from 0100 to 0101 — one certain outcome before, one certain outcome after, no superposition either side.
Applies the Quantum Fourier Transform, spreading the single input state into an equal-magnitude superposition over all 16 outputs, each carrying a different phase.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
Applies the exact inverse QFT, which collapses the superposition straight back to the original input.
Probability gathers from 16 outcomes onto 1. 0101 goes from 6.3% to 100.0%.
Readout The register reads 0101 again, exactly: the QFT and its inverse cancel, the way any unitary and its adjoint do.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupStated by the primary source: "These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters."
- Reported costTime polynomial in n and 1/ε to obtain any matrix element of any irreducible representation of the symmetric or alternating group to within ±ε, and likewise for any irreducible representation of polynomial highest weight of the unitary, special unitary and special orthogonal groups. The Hadamard test itself needs O(1/ε²) measurements.
- Papers1
Estimate a matrix element of a unitary irreducible representation of a group — a single entry of a matrix whose dimension may be exponentially large — to within an additive error, for the symmetric and alternating groups and for the unitary, special unitary and special orthogonal groups of polynomial highest weight. Everything routes through the Hadamard test, which turns an efficient circuit for a unitary together with efficient state preparation into an additive estimate of an expectation value. For a finite group with an efficient quantum Fourier transform, conjugating the regular representation by the transform yields the direct sum of all irreducible representations, which gives the matrix elements. For the unitary and symmetric groups jointly, the quantum Schur transform block-diagonalizes both actions at once. For the Lie groups of polynomial highest weight, the matrix elements come from simulating a sparse, row-computable Hamiltonian built from Gel'fand-Tsetlin generators. For the symmetric and alternating groups directly, a permutation is decomposed into neighbour transpositions by bubblesort, and the Young-Yamanouchi representation of a neighbour transposition is a simple direct sum of small blocks.
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 →
Everything routes through the Hadamard test, which turns an efficient circuit for a unitary together with efficient state preparation into an additive estimate of an expectation value. For a finite group with an efficient quantum Fourier transform, conjugating the regular representation by the transform yields the direct sum of all irreducible representations, which gives the matrix elements. For the unitary and symmetric groups jointly, the quantum Schur transform block-diagonalizes both actions at once. For the Lie groups of polynomial highest weight, the matrix elements come from simulating a sparse, row-computable Hamiltonian built from Gel'fand-Tsetlin generators. For the symmetric and alternating groups directly, a permutation is decomposed into neighbour transpositions by bubblesort, and the Young-Yamanouchi representation of a neighbour transposition is a simple direct sum of small blocks. This record's speedup class, "Superpolynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.". Reported cost: Time polynomial in n and 1/ε to obtain any matrix element of any irreducible representation of the symmetric or alternating group to within ±ε, and likewise for any irreducible representation of polynomial highest weight of the unitary, special unitary and special orthogonal groups. The Hadamard test itself needs O(1/ε²) measurements..
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)
- Superpolynomial
- Primary source on the speedup
- Stated by the primary source: "These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters."
- Reported cost
- Time polynomial in n and 1/ε to obtain any matrix element of any irreducible representation of the symmetric or alternating group to within ±ε, and likewise for any irreducible representation of polynomial highest weight of the unitary, special unitary and special orthogonal groups. The Hadamard test itself needs O(1/ε²) measurements.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which states it)
- Complexity basis
- section 1 of arXiv:0811.0562: "for the finite groups Sn and An we obtain any matrix element of any irreducible representation to within ±ǫ in time that scales polynomially in 1/ǫ and n. For the Lie groups U(n), SU(n), and SO(n) we obtain any matrix element of any irreducible representation of polynomial highest weight to within ±ǫ in time that scales polynomially in 1/ǫ and n."; section 5: "quantum computers can solve the following problem with probability 1 − δ in poly(n, 1/ǫ, log(1/δ)) time."; section 2, for the subroutine: "one can obtain the real part of ⟨ψ|U|ψ⟩ to precision ǫ by making O(1/ǫ²) measurements."
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum Fourier transform 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: Matrix elements of irreducible group representations
PROBLEM: Estimate a matrix element of a unitary irreducible representation of a group — a single entry of a matrix whose dimension may be exponentially large — to within an additive error, for the symmetric and alternating groups and for the unitary, special unitary and special orthogonal groups of polynomial highest weight.
IDEA: Everything routes through the Hadamard test, which turns an efficient circuit for a unitary together with efficient state preparation into an additive estimate of an expectation value. For a finite group with an efficient quantum Fourier transform, conjugating the regular representation by the transform yields the direct sum of all irreducible representations, which gives the matrix elements. For the unitary and symmetric groups jointly, the quantum Schur transform block-diagonalizes both actions at once. For the Lie groups of polynomial highest weight, the matrix elements come from simulating a sparse, row-computable Hamiltonian built from Gel'fand-Tsetlin generators. For the symmetric and alternating groups directly, a permutation is decomposed into neighbour transpositions by bubblesort, and the Young-Yamanouchi representation of a neighbour transposition is a simple direct sum of small blocks.
REPORTED COST: Time polynomial in n and 1/ε to obtain any matrix element of any irreducible representation of the symmetric or alternating group to within ±ε, and likewise for any irreducible representation of polynomial highest weight of the unitary, special unitary and special orthogonal groups. The Hadamard test itself needs O(1/ε²) measurements.
BASIS: section 1 of arXiv:0811.0562: "for the finite groups Sn and An we obtain any matrix element of any irreducible representation to within ±ǫ in time that scales polynomially in 1/ǫ and n. For the Lie groups U(n), SU(n), and SO(n) we obtain any matrix element of any irreducible representation of polynomial highest weight to within ±ǫ in time that scales polynomially in 1/ǫ and n."; section 5: "quantum computers can solve the following problem with probability 1 − δ in poly(n, 1/ǫ, log(1/δ)) time."; section 2, for the subroutine: "one can obtain the real part of ⟨ψ|U|ψ⟩ to precision ǫ by making O(1/ǫ²) measurements."
PRIMARY SOURCE: Stephen P. Jordan (2008), Fast quantum algorithms for approximating some irreducible representations of groups — https://arxiv.org/abs/0811.0562
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.
Related entries
References
- Fast quantum algorithms for approximating some irreducible representations of groups
Stephen P. Jordan · 2008
Primary source, and the source of this record's cost claim. Consult it for section 5 above all, where the additive-approximation caveat is worked out — the typical matrix element of an exponentially large representation is exponentially small, so the average case is classically easy and the paper's own hardness claim is an unproven hypothesis rather than a theorem. Note the title: the paper says "some irreducible representations" where the Zoo's citation says "the irreducible representations".