A promise BQP-complete string rewriting problem

Janzing, D; Wocjan, P

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

学術論文

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
(出版社版)

Fulltext (restricted access)

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

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

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.

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