Hannover 2016 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

Q: Fachverband Quantenoptik und Photonik

Q 8: Quantum Information: Concepts and Methods II

Q 8.1: Vortrag

Montag, 29. Februar 2016, 14:30–14:45, e214

Quantum Complexity Classes with Disturbed Witnesses — •Friederike Anna Dziemba and Tobias Osborne — Insitut für Theoretische Physik, Leibniz Universität Hannover, Germany

Quantum complexity theory categorizes computational problems into complexity classes characterized by a specific type of quantum protocol. The most famous classes are formed by the problems that can be solved efficiently by a quantum computer (class BQP) and the problems that can be verified efficiently by a quantum computer provided with a so-called witness which can either be a quantum or a classical state (classes QMA or QCMA).

We consider these three classes as variants of a complexity class defined by an efficient quantum protocol and a witness that is sent through a parametrized quantum channel. Depending on the noise the channel introduces into the witness we reobtain either the class QMA, QCMA or BQP. Thresholds for the channel parameter guaranteeing one of these cases allow for new characterizations of the standard complexity classes.