Algorithms · PromiseBQP-complete problem
Quadratically signed weight enumerators
A quadratically signed weight enumerator is the sum S(A, B, x, y) = Σ (−1)^(bᵀBb) x^|b| y^(n−|b|) over the 0/1 vectors b with Ab = 0. Given that the diagonal of A is the identity, that k and l are positive integers, and a promise that |S(A, lwtr(A), k, l)| is at least (k² + l²)^(n/2)/2, determine the sign of S.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot stated by the primary source — the full text of arXiv:quant-ph/9909094 — abstract, sections I through V and appendix A. The paper's claim is a polynomial-equivalence and BQP-completeness result, not a speedup: an oracle for the sign problem makes classical probabilistic computation as powerful as quantum computation. No statement anywhere compares a quantum algorithm's cost with a classical algorithm's cost for a shared task. was read and makes no such claim
- Reported costNot stated by the sources read
- Papers1
A quadratically signed weight enumerator is the sum S(A, B, x, y) = Σ (−1)^(bᵀBb) x^|b| y^(n−|b|) over the 0/1 vectors b with Ab = 0. Given that the diagonal of A is the identity, that k and l are positive integers, and a promise that |S(A, lwtr(A), k, l)| is at least (k² + l²)^(n/2)/2, determine the sign of S. Knill and Laflamme expand a quantum circuit's amplitude by multiplying out its gate sequence, writing each gate as (4 + 3σ̃)/5 so that the product becomes a sum over 0/1 vectors with signs given by a quadratic form. That sum is then recognized as an instance of the quadratically signed weight enumerator above. The two directions follow: an oracle deciding the sign of such a sum lets a classical probabilistic machine simulate a quantum computer, and conversely a quantum computer can decide the sign under the promise, so the problem is BQP-complete. A more restricted variant is shown to be solvable by the one-bit model of quantum computation, in which only a single qubit is initialized and the rest of the register is maximally mixed. The paper is a bridge between quantum computation and a purely combinatorial quantity, not a faster way of computing anything.
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 →
Knill and Laflamme expand a quantum circuit's amplitude by multiplying out its gate sequence, writing each gate as (4 + 3σ̃)/5 so that the product becomes a sum over 0/1 vectors with signs given by a quadratic form. That sum is then recognized as an instance of the quadratically signed weight enumerator above. The two directions follow: an oracle deciding the sign of such a sum lets a classical probabilistic machine simulate a quantum computer, and conversely a quantum computer can decide the sign under the promise, so the problem is BQP-complete. A more restricted variant is shown to be solvable by the one-bit model of quantum computation, in which only a single qubit is initialized and the rest of the register is maximally mixed. The paper is a bridge between quantum computation and a purely combinatorial quantity, not a faster way of computing anything. 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 stated by the primary source — the full text of arXiv:quant-ph/9909094 — abstract, sections I through V and appendix A. The paper's claim is a polynomial-equivalence and BQP-completeness result, not a speedup: an oracle for the sign problem makes classical probabilistic computation as powerful as quantum computation. No statement anywhere compares a quantum algorithm's cost with a classical algorithm's cost for a shared task. was read and makes no such claim. The sources read state no complexity bound for this record (The source states no complexity bound for this record, because its results are equivalence and completeness theorems rather than an algorithm with a runtime. The only asymptotic figures in the text are internal steps: section III, proof of Theorem 7 — "By using binary search on x, the desired probability can be determined to within O(ǫ/N) in O(log(N/ǫ)) queries" — and section IV — "these gates can be approximated to within O(ǫ/N) using the standard ones with polylog(N/ǫ) overhead in gates". Read for this: the abstract, sections I through V and appendix A.).
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 stated by the primary source — the full text of arXiv:quant-ph/9909094 — abstract, sections I through V and appendix A. The paper's claim is a polynomial-equivalence and BQP-completeness result, not a speedup: an oracle for the sign problem makes classical probabilistic computation as powerful as quantum computation. No statement anywhere compares a quantum algorithm's cost with a classical algorithm's cost for a shared task. was read and makes no such claim
- Reported cost
- Not stated by the sources read
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which does not state it)
- Complexity basis
- The source states no complexity bound for this record, because its results are equivalence and completeness theorems rather than an algorithm with a runtime. The only asymptotic figures in the text are internal steps: section III, proof of Theorem 7 — "By using binary search on x, the desired probability can be determined to within O(ǫ/N) in O(log(N/ǫ)) queries" — and section IV — "these gates can be approximated to within O(ǫ/N) using the standard ones with polylog(N/ǫ) overhead in gates". Read for this: the abstract, sections I through V and appendix A.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare PromiseBQP-complete problem 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: Quadratically signed weight enumerators
PROBLEM: A quadratically signed weight enumerator is the sum S(A, B, x, y) = Σ (−1)^(bᵀBb) x^|b| y^(n−|b|) over the 0/1 vectors b with Ab = 0. Given that the diagonal of A is the identity, that k and l are positive integers, and a promise that |S(A, lwtr(A), k, l)| is at least (k² + l²)^(n/2)/2, determine the sign of S.
IDEA: Knill and Laflamme expand a quantum circuit's amplitude by multiplying out its gate sequence, writing each gate as (4 + 3σ̃)/5 so that the product becomes a sum over 0/1 vectors with signs given by a quadratic form. That sum is then recognized as an instance of the quadratically signed weight enumerator above. The two directions follow: an oracle deciding the sign of such a sum lets a classical probabilistic machine simulate a quantum computer, and conversely a quantum computer can decide the sign under the promise, so the problem is BQP-complete. A more restricted variant is shown to be solvable by the one-bit model of quantum computation, in which only a single qubit is initialized and the rest of the register is maximally mixed. The paper is a bridge between quantum computation and a purely combinatorial quantity, not a faster way of computing anything.
REPORTED COST: Not stated by the sources read
BASIS: The source states no complexity bound for this record, because its results are equivalence and completeness theorems rather than an algorithm with a runtime. The only asymptotic figures in the text are internal steps: section III, proof of Theorem 7 — "By using binary search on x, the desired probability can be determined to within O(ǫ/N) in O(log(N/ǫ)) queries" — and section IV — "these gates can be approximated to within O(ǫ/N) using the standard ones with polylog(N/ǫ) overhead in gates". Read for this: the abstract, sections I through V and appendix A.
PRIMARY SOURCE: E. Knill, R. Laflamme (1999), Quantum Computation and Quadratically Signed Weight Enumerators — https://arxiv.org/abs/quant-ph/9909094
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
- Quantum Computation and Quadratically Signed Weight Enumerators
E. Knill, R. Laflamme · 1999
Primary source. Consult it for the expansion of a circuit amplitude into a signed sum over 0/1 vectors, for the exact promise the completeness results are stated under, and for the authors' own remark in the conclusion that this promise may be difficult to verify — which is the reason this record carries no complexity and makes no speedup claim.