Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  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

Basisdaten

einblenden: ausblenden:
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
https://dl.acm.org/citation.cfm?id=2011355 (Verlagsversion)
Beschreibung:
-
OA-Status:

Urheber

einblenden:
ausblenden:
 Urheber:
Janzing, D1, 2, Autor           
Wocjan, P, Autor
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              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n):
 Datum: 2010-03
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: -
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Quantum Information and Computation
  Andere : Quantum Inform. Comput.
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Princeton, NJ : Rinton Press
Seiten: - Band / Heft: 10 (3) Artikelnummer: - Start- / Endseite: 234 - 257 Identifikator: ISSN: 1533-7146
CoNE: https://pure.mpg.de/cone/journals/resource/111019684377004