Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

A promise BQP-complete string rewriting problem


Janzing,  D
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

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