A promise BQP-complete string rewriting problem

Janzing, D; Wocjan, P

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

A promise BQP-complete string rewriting problem

MPS-Authors

/persons/resource/persons75626

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

https://dl.acm.org/citation.cfm?id=2011355
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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: https://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.