Algorithms · Topological invariants
Additive approximation of Turaev-Viro 3-manifold invariants
Given a compact, orientable three-manifold presented by a Heegaard splitting, compute a certain additive approximation to its Turaev-Viro invariant, the scalar topological invariant that takes the same value on homeomorphic manifolds.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costNot stated by the sources read
- Papers1
Given a compact, orientable three-manifold presented by a Heegaard splitting, compute a certain additive approximation to its Turaev-Viro invariant, the scalar topological invariant that takes the same value on homeomorphic manifolds. The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds, and Alagic, Jordan, Koenig and Reichardt give a quantum algorithm that additively approximates them for a manifold presented by a Heegaard splitting. The paper describes the algorithm as motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. The abstract states that its accuracy is shown to be nontrivial in the following sense: the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer, so approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation, which the Zoo records by saying that this approximation is BQP-complete. The Zoo sets the result beside an earlier polynomial-time quantum algorithm that additively approximates the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation, notes that squaring the WRT invariant yields the Turaev-Viro invariant, and states that whether the earlier approximation is BQP-complete is unknown.
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 Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds, and Alagic, Jordan, Koenig and Reichardt give a quantum algorithm that additively approximates them for a manifold presented by a Heegaard splitting. The paper describes the algorithm as motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. The abstract states that its accuracy is shown to be nontrivial in the following sense: the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer, so approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation, which the Zoo records by saying that this approximation is BQP-complete. The Zoo sets the result beside an earlier polynomial-time quantum algorithm that additively approximates the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation, notes that squaring the WRT invariant yields the Turaev-Viro invariant, and states that whether the earlier approximation is BQP-complete is unknown. This record's speedup class, "Superpolynomial", is a secondary source's classification of the approximation and simulation algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. The sources read state no complexity bound for this record (Two sources were read and neither states a cost for this algorithm. The abstract of arXiv:1003.0923 quotes no running time, query count, gate count or qubit count: it says only "We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting" and that "the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer". The Quantum Algorithm Zoo entry "Three-manifold Invariants" is likewise unquantified for this result: "a quantum computer can efficiently find a certain additive approximation to its Turaev-Viro invariant, and this approximation is BQP-complete [ 129 ]." The only clause in that entry naming a running time belongs to a different algorithm in a different reference — "Earlier, in [ 114 ], a polynomial-time quantum algorithm was given to additively approximate the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation" — and that paper is not part of this record, so its bound is not carried over here. BQP-completeness is a statement of hardness rather than a cost, so the field is left empty rather than filled from elsewhere.).
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
- Not checked against the primary source yet
- Reported cost
- Not stated by the sources read
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Two sources were read and neither states a cost for this algorithm. The abstract of arXiv:1003.0923 quotes no running time, query count, gate count or qubit count: it says only "We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting" and that "the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer". The Quantum Algorithm Zoo entry "Three-manifold Invariants" is likewise unquantified for this result: "a quantum computer can efficiently find a certain additive approximation to its Turaev-Viro invariant, and this approximation is BQP-complete [ 129 ]." The only clause in that entry naming a running time belongs to a different algorithm in a different reference — "Earlier, in [ 114 ], a polynomial-time quantum algorithm was given to additively approximate the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation" — and that paper is not part of this record, so its bound is not carried over here. BQP-completeness is a statement of hardness rather than a cost, so the field is left empty rather than filled from elsewhere.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Topological invariants 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: Additive approximation of Turaev-Viro 3-manifold invariants
PROBLEM: Given a compact, orientable three-manifold presented by a Heegaard splitting, compute a certain additive approximation to its Turaev-Viro invariant, the scalar topological invariant that takes the same value on homeomorphic manifolds.
IDEA: The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds, and Alagic, Jordan, Koenig and Reichardt give a quantum algorithm that additively approximates them for a manifold presented by a Heegaard splitting. The paper describes the algorithm as motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. The abstract states that its accuracy is shown to be nontrivial in the following sense: the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer, so approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation, which the Zoo records by saying that this approximation is BQP-complete. The Zoo sets the result beside an earlier polynomial-time quantum algorithm that additively approximates the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation, notes that squaring the WRT invariant yields the Turaev-Viro invariant, and states that whether the earlier approximation is BQP-complete is unknown.
REPORTED COST: Not stated by the sources read
BASIS: Two sources were read and neither states a cost for this algorithm. The abstract of arXiv:1003.0923 quotes no running time, query count, gate count or qubit count: it says only "We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting" and that "the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer". The Quantum Algorithm Zoo entry "Three-manifold Invariants" is likewise unquantified for this result: "a quantum computer can efficiently find a certain additive approximation to its Turaev-Viro invariant, and this approximation is BQP-complete [ 129 ]." The only clause in that entry naming a running time belongs to a different algorithm in a different reference — "Earlier, in [ 114 ], a polynomial-time quantum algorithm was given to additively approximate the Witten-Reshitikhin-Turaev (WRT) invariant of a manifold given by a surgery presentation" — and that paper is not part of this record, so its bound is not carried over here. BQP-completeness is a statement of hardness rather than a cost, so the field is left empty rather than filled from elsewhere.
PRIMARY SOURCE: Gorjan Alagic, Stephen P. Jordan, Robert Koenig, Ben W. Reichardt (2010), Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation — https://arxiv.org/abs/1003.0923
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
- Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
Gorjan Alagic, Stephen P. Jordan, Robert Koenig, Ben W. Reichardt · 2010
Primary source: it gives the quantum algorithm that additively approximates Turaev-Viro invariants of a manifold presented by a Heegaard splitting, motivates the construction by the relationship between topological quantum computers and (2+1)-D topological quantum field theories, and establishes that approximating certain such invariants is a universal problem for quantum computation, which it presents as a novel relation between distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. Consult it for the accuracy the approximation achieves and for the classical preprocessing the universality claim assumes, since the abstract quantifies neither and states no running time.