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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
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.
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.).
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.
Compare PromiseBQP-complete problem with the strongest classical method for the same instance, input budget, and output metric.
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
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.
arxiv.org/abs/quant-ph/9909094 ↗