Algorithms · PromiseBQP-complete problem
String rewriting derivation counts
Fix a relation that permits replacing one substring by another. Given strings s, t and t′ of length L, let Δ(n) be the number of ways of reaching t from s in exactly n replacements minus the number of ways of reaching t′. Given a promise that |Δ(m)| ≥ εc^m for the input m, and a growth promise that Δ(n) ≤ c^n for every n, determine the sign of Δ(m).
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupStated by the primary source: "Given that BQP≠BPP, our result shows that the quantum computer outperforms the classical computer in estimating differences of combinatorial quantities."
- Reported costNot stated by the sources read
- Papers1
A part this method uses, worked through
This page says Hamiltonian simulation and phase estimation can estimate
— here is a concrete, runnable instance of it.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Where it ends up
- 1011100%
The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioA part this method uses, worked through
This page says Hamiltonian simulation and phase estimation
— here is a concrete, runnable instance of it.
2 Trotter steps of a transverse-field Ising chain
4 qubits starting at |0000⟩, J=1, h=0.5, dt=0.3, 2 first-order Trotter steps.
Where it ends up
- 000075%
- 00016%
- 10006%
- 00105%
- 12 more outcomes8%
The state spreads from |0000⟩ across several nearby basis states. The exact split is a regression value from this file's own simulator, not a claim about a real material.
Open this part in StudioFix a relation that permits replacing one substring by another. Given strings s, t and t′ of length L, let Δ(n) be the number of ways of reaching t from s in exactly n replacements minus the number of ways of reaching t′. Given a promise that |Δ(m)| ≥ εc^m for the input m, and a growth promise that Δ(n) ≤ c^n for every n, determine the sign of Δ(m). The replacement relation defines an adjacency matrix A on strings, and Δ(m) becomes a difference of expectation values of A^m in the two states (|s⟩ ± |φ⟩)/√2, which Hamiltonian simulation and phase estimation can estimate. Rather than estimating A^m directly the algorithm estimates a Lipschitz-clipped function of A, clipped at ±c^m, and it is this clipping that lets the growth promise control the error. The hardness direction encodes an arbitrary quantum circuit into a translationally invariant, finite-range Hamiltonian on a chain of qudits — program, data and auxiliary bands, using only Toffoli and Hadamard gates — and shows that an entry of a power of that Hamiltonian equals the circuit's difference of accepting and rejecting probabilities. A final step converts the Hamiltonian into a genuine 0/1 adjacency matrix by adding a simulator band that absorbs the ±1/√2 entries the Hadamard gate contributes. The authors are explicit that this is not a corollary of their own earlier sparse-matrix result: string rewriting appears as an instance of that problem only if one neglects the promises, so the entire argument had to be reworked.
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 replacement relation defines an adjacency matrix A on strings, and Δ(m) becomes a difference of expectation values of A^m in the two states (|s⟩ ± |φ⟩)/√2, which Hamiltonian simulation and phase estimation can estimate. Rather than estimating A^m directly the algorithm estimates a Lipschitz-clipped function of A, clipped at ±c^m, and it is this clipping that lets the growth promise control the error. The hardness direction encodes an arbitrary quantum circuit into a translationally invariant, finite-range Hamiltonian on a chain of qudits — program, data and auxiliary bands, using only Toffoli and Hadamard gates — and shows that an entry of a power of that Hamiltonian equals the circuit's difference of accepting and rejecting probabilities. A final step converts the Hamiltonian into a genuine 0/1 adjacency matrix by adding a simulator band that absorbs the ±1/√2 entries the Hadamard gate contributes. The authors are explicit that this is not a corollary of their own earlier sparse-matrix result: string rewriting appears as an instance of that problem only if one neglects the promises, so the entire argument had to be reworked. 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. Stated by the primary source: "Given that BQP≠BPP, our result shows that the quantum computer outperforms the classical computer in estimating differences of combinatorial quantities.". The sources read state no complexity bound for this record (The source states no resource bound for this record. arXiv:0705.1180 section 3 gives an accuracy rather than a cost — "we obtain an estimation of ∆s,t,t′(m) up to an error of ǫc^m with any desired probability that is inverse polynomially close to 1" — and defers the circuit itself: "It is straightforward but technical to construct a quantum circuit ... that it solves String Rewriting in the sense of Definition 2." Read for this: the abstract, sections 1, 2, 3 and 5, and the definitions and footnotes in section 2. Note also that the abstract and the body disagree on how m may grow — the abstract says "an integer m that is polylog- arithmic in L", while Definition 1 in section 2 takes "a positive integer m = poly(L) as input" — so no growth rate for m is stated here either.).
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: "Given that BQP≠BPP, our result shows that the quantum computer outperforms the classical computer in estimating differences of combinatorial quantities."
- Reported cost
- Not stated by the sources read
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which states it)
- Complexity basis
- The source states no resource bound for this record. arXiv:0705.1180 section 3 gives an accuracy rather than a cost — "we obtain an estimation of ∆s,t,t′(m) up to an error of ǫc^m with any desired probability that is inverse polynomially close to 1" — and defers the circuit itself: "It is straightforward but technical to construct a quantum circuit ... that it solves String Rewriting in the sense of Definition 2." Read for this: the abstract, sections 1, 2, 3 and 5, and the definitions and footnotes in section 2. Note also that the abstract and the body disagree on how m may grow — the abstract says "an integer m that is polylog- arithmic in L", while Definition 1 in section 2 takes "a positive integer m = poly(L) as input" — so no growth rate for m is stated here either.
- 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: String rewriting derivation counts
PROBLEM: Fix a relation that permits replacing one substring by another. Given strings s, t and t′ of length L, let Δ(n) be the number of ways of reaching t from s in exactly n replacements minus the number of ways of reaching t′. Given a promise that |Δ(m)| ≥ εc^m for the input m, and a growth promise that Δ(n) ≤ c^n for every n, determine the sign of Δ(m).
IDEA: The replacement relation defines an adjacency matrix A on strings, and Δ(m) becomes a difference of expectation values of A^m in the two states (|s⟩ ± |φ⟩)/√2, which Hamiltonian simulation and phase estimation can estimate. Rather than estimating A^m directly the algorithm estimates a Lipschitz-clipped function of A, clipped at ±c^m, and it is this clipping that lets the growth promise control the error. The hardness direction encodes an arbitrary quantum circuit into a translationally invariant, finite-range Hamiltonian on a chain of qudits — program, data and auxiliary bands, using only Toffoli and Hadamard gates — and shows that an entry of a power of that Hamiltonian equals the circuit's difference of accepting and rejecting probabilities. A final step converts the Hamiltonian into a genuine 0/1 adjacency matrix by adding a simulator band that absorbs the ±1/√2 entries the Hadamard gate contributes. The authors are explicit that this is not a corollary of their own earlier sparse-matrix result: string rewriting appears as an instance of that problem only if one neglects the promises, so the entire argument had to be reworked.
REPORTED COST: Not stated by the sources read
BASIS: The source states no resource bound for this record. arXiv:0705.1180 section 3 gives an accuracy rather than a cost — "we obtain an estimation of ∆s,t,t′(m) up to an error of ǫc^m with any desired probability that is inverse polynomially close to 1" — and defers the circuit itself: "It is straightforward but technical to construct a quantum circuit ... that it solves String Rewriting in the sense of Definition 2." Read for this: the abstract, sections 1, 2, 3 and 5, and the definitions and footnotes in section 2. Note also that the abstract and the body disagree on how m may grow — the abstract says "an integer m that is polylog- arithmic in L", while Definition 1 in section 2 takes "a positive integer m = poly(L) as input" — so no growth rate for m is stated here either.
PRIMARY SOURCE: Dominik Janzing, Pawel Wocjan (2007), A PromiseBQP-complete String Rewriting Problem — https://arxiv.org/abs/0705.1180
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.
Where this sits
This record is named by the layer graph at:
- Estimate the eigenphase of a unitary Slot
Takes A circuit for U that can be applied as controlled U^(2^j), a preparation routine for a state whose overlap with the target eigenvector is not negligible, the number of bits of the phase wanted, and the failure probability that may be tolerated. Returns An estimate of the eigenphase to the requested number of bits, with the failure probability it was obtained at, plus the two costs that actually differ between routes: how many ancillas were held at once, and how many sequential rounds were run.
Related entries
References
- A PromiseBQP-complete String Rewriting Problem
Dominik Janzing, Pawel Wocjan · 2007
Primary source. Consult it for the two promises the result depends on, for the Lipschitz clipping that makes the growth promise usable, and for the encoding of a quantum circuit into a translationally invariant qudit chain. It is also the place to check the disagreement between the abstract and Definition 1 about how the power m may grow with the string length, which is why this record states no cost.