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). 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.

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

Quantum vs classical

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.

Related entries

• Diagonal entries of powers of a sparse symmetric matrix

  Algorithms

• Additive approximation of the Jones polynomial at a primitive root of unity

  Algorithms

• Quantum phase estimation

  Algorithms