printlogo
http://www.ethz.ch/index_EN
International Workshop on Quantum Information Processing
 
print
  

QIP 2010 at

ETH Life

The daily web-journal of ETH Zurich:

"Lifting the big veil"

"Nach dem grossen Schleier lüften"

18.01.2010

QIP 2010 at the

Swiss Radio DRS

Echo der Zeit

from Monday Jan 18, 2010

in German, Link >>

(Real Player recommended)

chocolate


pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

pauliohne


The Swiss National Science Foundation

snflogo


ETH Zurich (Computer Science and Physics Department)

ethlogo


Quantum Science and Technology

qsitmitschrift


CQT Singapore

cqtlogo


QAP European Project

qaplogo3


Sandia National Laboratories

sandia


Institute for Quantum Computing

finaliqc


id Quantique

3rdideequantique

Laying the quantum and classical embedding problems to rest

Toby Cubitt, Bristol

joint work with Jens Eisert and Michael Wolf

Quantum channels and master equations are both widely used to describe the dynamics of quantum systems that are subject to noise. Quantum channels, also known as completely-positive maps, are commonly used in quantum information theory, where abstracting away the underlying physics allows one to focus on the information-theoretic aspects of noise. Master equations are frequently used in physics, where the underlying physical processes are the main focus of attention. The connection between these two descriptions is a classic topic in mathematical physics. One direction was solved by the now famous result due to Lindblad, Kossakowski and Gorini, who gave a complete characterisation of master equations that generate completely positive evolutions. However, the other direction has remained open: given a quantum channel, is there a master equation that generates it (and if so, can we deduce it's form)? Physically, this is asking how one can deduce underlying physical processes from experimental observations.

The analogous question can equally well be posed in classical dynamics: given a stochastic map, does there exist a continuous-time Markov chain that generates it? This is known in probability theory as the embedding problem, and it is even older than the quantum version; it was first studied at least as far back as 1937. It too has remained an open problem to this day. In this work, we give complexity theoretic solutions to both the quantum and classical embedding problems: both problems are NP-hard. Moreover, we give an explicit algorithm that reduces the problem to integer semi-definite programming, completing the proof that solving the quantum or classical embedding problem is equivalent to solving P=NP, thus finally laying the embedding problem to rest after more than 70 years.

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2013 ETH Zürich | Imprint | Disclaimer | 5 January 2010
top