English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A promise BQP-complete string rewriting problem

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

Item is

Basic

show hide
Genre: Journal Article

Files

show Files

Locators

show
hide
Locator:
https://dl.acm.org/citation.cfm?id=2011355 (Publisher version)
Description:
-

Creators

show
hide
 Creators:
Janzing, D1, 2, Author              
Wocjan, P, Author
Affiliations:
1Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              
2Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497795              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s):
 Dates: 2010-03
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: -
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Quantum Information and Computation
  Other : Quantum Inform. Comput.
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Princeton, NJ : Rinton Press
Pages: - Volume / Issue: 10 (3) Sequence Number: - Start / End Page: 234 - 257 Identifier: ISSN: 1533-7146
CoNE: https://pure.mpg.de/cone/journals/resource/111019684377004