◐Attested & literatureAlgorithmsPromiseBQP-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).
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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). 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.
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 →
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.
How it works
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.).
Implementation
Unsupported
string-rewriting-derivation-counts.txt
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 1in 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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
A PromiseBQP-complete String Rewriting Problem2007 · Dominik Janzing, Pawel Wocjan
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.