# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### A promise BQP-complete string rewriting problem

##### External Resource

https://dl.acm.org/citation.cfm?id=2011355

(Publisher version)

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Janzing, D., & Wocjan, P. (2010). A promise BQP-complete string rewriting problem.* Quantum Information and Computation,* *10*(3), 234-257.

Cite as: http://hdl.handle.net/21.11116/0000-0002-7726-E

##### Abstract

We consider the following combinatorial problem. We are given three strings s, t, and t'of length L over some fixed finite alphabet and an integer m that is polylogarithmic inL. We have a symmetric relation on substrings of constant length that specifies whichsubstrings are allowed to be replaced with each other. Let Δ(n) denote the differencebetween the numbers of possibilities to obtain t from s, and t' from s after n ∈ Nreplacements. The problem is to determine the sign of Δ(m). As promises we have agap condition and a growth condition. The former states that |Δ(m)| ≥ εcm where ε isinverse polylogarithmic in L and c > 0 is a constant. The latter is given by Δ(n) ≤ cnfor all n. We show that this problem is PromiseBQP-complete, i.e., it represents theclass of problems that can be solved efficiently on a quantum computer.