log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
PhD Defense: The membership problem for constant-sized quantum correlations is undecidable
Hong Hao Fu
Remote
Friday, April 9, 2021, 11:00 am-1:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract
One of the most fundamental and counterintuitive features of quantum mechanics is entanglement, which is central to many demonstrations of the quantum advantage. Studying quantum correlations generated by local measurements on an entangled physical system is one of the direct ways to gain insights into entanglement. The focus of this dissertation is to get better understanding of the hardness of determining if a given correlation is quantum, which is also known as the membership problem of quantum correlations.

Previous work has shown that the general membership problem is computationally undecidable. Where does the hardness come from? Is it just because the size of a quantum correlation (i.e., the number of real values in the description of the correlation) can be arbitrarily large? We would like to understand the role played by the varying sizes of correlations in the hardness of the membership problem.

It has been shown that certain quantum correlations require the measured quantum system to be maximally entangled with a certain dimension. This is a unique phenomenon of quantum correlations and it is known as self-testing. The first step towards answering the hardness of the membership problem of quantum correlations is to get deeper understandings about self-testing, and more specifically, about the size of a correlation that can self-test a maximally entangled state of arbitrarily large dimension. If correlations of a fixed size can self-test entangled states of unbounded dimension, this phenomenon is a strong evidence suggesting that deciding membership of fixed-sized correlations can be very hard.

We first show that there exists an infinite subset of the set of all the prime numbers such that, for each prime p in this set, a maximally entangled state of local dimension (p-1) can be self-tested by a correlation of a fixed size. Since this set is infinite, this result implies that constant-sized correlations are sufficient to self-test maximally entangled states of unbounded dimension.

Building on the self-testing result, we show that the varying sizes of correlations are not the only root of the hardness. Specifically, we show that the membership problem of fixed finite-sized correlations is still computationally undecidable when the fixed size is sufficiently large. That is, the hardness of the membership problem of quantum correlations is independent of the varying sizes of correlations. In fact, the hardness arises from the fact that the structure of some set of correlations of a particular size is so complicated that no finite description of this set can allow a Turing machine to decide if a correlation is quantum or not.

Examining Committee: 
 
                           Chair:              Dr. Andrew M. Childs                   
                           Co-Chair:      Dr.  Carl A. Miller 
                           Dean's rep:      Dr. Jonathan M. Rosenberg
                          Members:         Dr.  Xiaodi Wu 
                                                Dr.  Yi-Kai Liu
Bio
Honghao Fu is a Ph.D. student at the University of Maryland's Department of Computer Science, working under the supervision of Prof. Carl Miller. He is interested in questions about quantum correlations and, in particular, the complexity aspect of quantum correlations.

 

This talk is organized by Tom Hurst