COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Two-message quantum interactive proofs and the quantum separability problem

## Two-message quantum interactive proofs and the quantum separability problemAdd to your list(s) Download to your calendar using vCal - Mark M. Wilde (McGill University)
- Friday 18 January 2013, 13:00-14:00
- MR14, Centre for Mathematical Sciences.
If you have a question about this talk, please contact Paul Skrzypczyk. Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with “quantum statistical zero knowledge” (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK -complete promise problem “quantum state distinguishability” to our quantum separability problem. By exploiting Knill’s efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK . We consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- MR14, Centre for Mathematical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsCambridge Evolutionary Genetics DPMMS PhD student colloquium Cambridge Public Policy Workshops Centre for Energy Studies DAMTP Visual Rhetoric and modern South Asian History, Michaelmas 2017## Other talksValidation & testing of novel therapeutic targets to treat osteosarcoma Random Feature Expansions for Deep Gaussian Processes What can we learn about cancer by modelling the data on it? Arithmetic and Dynamics on Markoff-Hurwitz Varieties Macrophage-derived extracellular succinate licenses neural stem cells to suppress chronic neuroinflammation Sustainability of livestock production: water, welfare and woodland PTPmesh: Data Center Network Latency Measurements Using PTP Glucagon like peptide-1 receptor - a possible role for beta cell physiology in susceptibility to autoimmune diabetes Graded linearisations for linear algebraic group actions Fumarate hydratase and renal cancer: oncometabolites and beyond Managing your research data effectively and working reproducibly for beginners |