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.
group representationmatrix elementschur transformhadamard testsymmetric group
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
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 →
How it works
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..
Implementation
Unsupported
irreducible-representation-matrix-elements.txt
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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Fast quantum algorithms for approximating some irreducible representations of groups2008 · Stephen P. Jordan
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".