Self-testing is a device-independent method to estimate the quantum state and operators inside a black box based on its observed behaviour. McKague et al. introduced a robust self-test of the singlet, showing that a black box that is close to the quantum bound for CHSH must be equivalent up to an isometry to a state close to the singlet with measurement operators close to the maximally violating ones. In this work, we extend Yang and Navascués' results on robust self-testing of partially entangled bipartite systems by completing their proof and showing that the measurement operators can also be self-tested. To do so, we study a set of decompositions in sums of squares (SOS) of the Bell operators defining a class of tilted CHSH inequalities whose maximally violating states contain all partially entangled qubit states.
New de Finetti theorems
Niel de Beaudrap
The problem 2-quantum-satisfiability (2-QSAT) is the generalisation of the 2-CNF-SAT problem to qubits, and is equivalent to determining whether or not a spin-1/2 Hamiltonian with two-body terms is frustration-free. Similarly to the classical problem #2-SAT, the counting problem #2-QSAT of determining the size (i.e. the dimension) of the set of satisfying states is #P-complete. However, if we consider random instances of 2-QSAT in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all two-qubit constraints are entangled, which more readily give rise to long-range constraints. We investigate under what conditions product constraints also give rise to families of #2-QSAT instances which are efficiently solvable, by considering #2-QSAT involving only discrete distributions over tensor product operators. This special case of #2-QSAT interpolates between classical #2-SAT, and #2-QSAT involving arbitrary product constraints. We find that such instances of #2-QSAT, defined on Erdős–Rényi graphs or bond-percolated lattices, are almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #2-SAT.
An interesting current open problem in quantum complexity theory is the quantum PCP conjecture. In analogy with the PCP theorem, the conjecture states that it is QMA-hard to tell whether a quantum constraint satisfaction problem (aka a local quantum Hamiltonian) is satisfiable or far from satisfiable, with a constant fraction of the constraints being violated in any assignment.
In this talk I will discuss limitations for quantum PCPs due to one of the most distinguishing features of quantum entanglement: its monogamous character. The monogamy of entanglement is the principle that the more entangled a system is with another one, the less entangled it can be with anything else. I will show how a quantitative understanding of entanglement monogamy leads both to limitations on the parameters that a potential quantum analogue of the PCP theorem might have, and to potential approaches to proving such an analogue (for instance by attempting to quantize the main steps of Dinur?s proof of the PCP theorem).
The talk will be mostly based on joint work with Aram Harrow (arXiv:1310.0017).
Semi-device-independent randomness generation
We provide a proof of existence of quantum weak coin flipping protocol with arbitrarily small bias. This proof is based on the work of Mochon, while some parts of it are simplified. Moreover, we provide an analysis of the number of qubits and rounds needed in the protocol as a function of the bias.
This is joint work with D. Aharonov, A. Chailloux, M. Ganz and L. Magnin
Johan Kok and Harmen van der Ven
QuantumAerospaceNow, an EU proposal on quantum algorithms for aerospace
The recent advances in quantum computers and quantum algorithms prompt the question which real-life applications will benefit from quantum computers. In this talk, we will present our EU proposal on quantum algorithms for aerospace. We will explain why we think aerospace is a relevant application domain for quantum computing. We will describe the proposed project and its objectives. We will finish with a description of existing algorithms and challenges in both computational fluid dynamics and computational electromagnetics.
An important aspect that sets quantum states apart from classical probability distributions is the possibility of two amplitudes to cancel each other out. However, many quantum phenomena do not take advantage of this feature and thus have a classical analogue. Collins and Popescu (2002) showed that teleportation and various entanglement manipulation protocols belong to this class of phenomena by establishing a close analogy between entanglement and secret classical correlations. We extend their framework by introducing a classical analogue of mixed quantum states. This yields new and even more striking classical analogues of quantum phenomena, such as private bound entanglement and superactivation of quantum capacity.
This talk is based on a joint work (http://arxiv.org/abs/1305.0848) with Graeme Smith and John Smolin from IBM.
An implicit assumption in the derivation of Bell inequalities, and hence the demonstration of quantum nonlocality, is that the measurement settings can be chosen freely. Here we show that this assumption can be relaxed almost completely, i.e. we show that quantum mechanics is nonlocal even with arbitrarily small freedom of choice. To this end, we prove that this type of correlations forms a polytope which we call the measurement dependent local (MDL) polytope. This gives rise to Bell-like inequalities whose violations are incompatible with the assumption of measurement dependent locality, i.e. Bell locality with limited free choice. Apart from fundamental interest, the MDL-polytope and its inequalities are prime candidates to be used in useful applications like randomness extraction or QKD.
Recently, Gallego et.al. proved that any future information principle aiming at distinguishing between quantum and post-quantum correlation must be intrinsically multipartite in nature. We establish similar result by using device independent success probability of Hardy's nonlocality argument for tripartite quantum system. We construct an example of a tri-partite Hardy correlation which is post-quantum but satisfies not only all bipartite information principle but also the GYNI inequality.
Practical DIQKD based only on causality.
We investigate the possibility of designing a noise-tolerant DIQKD protocol where Alice and Bob reuse their devices. In a protocol by Vazirani and Viddick the security of the key is based on the validity of quantum theory; we will discuss preliminary results which suggest the impossibility of such schemes when the validity of quantum theory is not required.
On the complexity of trial and error for constraint satisfaction problems
In this talk I will describe some results in a trial and error model of computing that was introduced by Bei, Chen and Zhang in STOC 2013, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying.
In a systematic study of constraint satisfaction problems we have defined several types of revealing oracles, and have developed a transfer theorem for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder CSP in the normal setting, such that their complexities are polynomial time equivalent. This in principle transfers the study of a large class of hidden CSPs, possibly with a promise on the instances, to the study of CSPs in the normal setting. The transfer theorems can be applied to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem.
I will also describe some recent results and ideas on the generalization of the model for probabilistic and quantum settings.
Based on joint works with I. Arad, A. Bouland, G. Ivanyos, R. Kulkarni, Y. Qiao and A. Sundaram.
True Randomness: Its Genesis and Expansion
Does near-perfect randomness exist in Nature, and if yes how can we obtain it in large quantities and under minimal assumptions? This question is not only fundamental to physics, but also vital to information processing. However, a satisfactory answer is
still elusive in practice and is beyond the reach of the classical theory of randomness extraction. Two recent thrusts of research --- randomness expansion and randomness amplification --- forged an exciting new path for a solution, where randomness is extracted from non-interacting and untrusted quantum devices, and security is based on the validity of physical theories.
In this talk, I will advocate a model of "physical randomness extractors" that unifies randomness expansion and the essence of amplification. I then provide our answer to the initial question: unless the world is deterministic, through such physical extractors that tolerate a constant level of device imperfection, near-perfect randomness can be created using a single and arbitrarily weak classical source, and be further expanded to an arbitrarily output length, at an exponential rate and securely against all-powerful quantum adversaries with a close-to-optimal security parameter. Additional new features achieved by those protocols include cryptographic quality of security, unit size quantum memory requirement for each device component, being adaptable for key distributions, and flexible in the construction building blocks. Those results widen the applications of physical extractors and facilitate their practical implementations.
I will also summarize our techniques for overcoming the many obstacles to establishing those results. A main problem left open is to construct a "perfect" physical extractor that optimizes all key parameters simultaneously, or to prove necessary tradeoffs among the parameters.
Based on joint works with Carl A. Miller (arXiv:1402.0489), Kai-Min Chung and Xiaodi Wu (arXiv:1402.4797).
Device-Independent Quantum Bit Commitment Using EPR Pairs
Establishing quantum entanglement between two distant parties is an essential step of many protocols in quantum information processing. One possibility for providing long-distance entanglement is to create an entangled composite state within a lab and then physically send one subsystem to a distant lab. Moreover, recent results show that entanglement distribution is even possible by sending a disentangled particle. In this talk we provide general limits for the amount of entanglement which can be distributed between two distant parties. One such limit is given by quantum discord. We also discuss the scenario where the exchanged particle is disentangled, and show that states of rank two cannot be used for entanglement distribution in this case.
One of the most important steps in the understanding of quantum many-body systems is due to the intensive studies of their entanglement properties. Much less, however, is known about the role of quantum nonlocality in these systems. This is because standard manybody observables involve correlations among few particles, while there is no multipartite Bell inequality for this scenario. Here we provide the first example of nonlocality detection in many-body systems using only two-body correlations. To this aim, we construct families of multipartite Bell inequalities that involve only second order correlations of local observables. We then provide examples of systems, relevant for nuclear and atomic physics, whose ground states violate our Bell inequalities for any number of constituents. Finally, we identify inequalities that can be tested by measuring collective spin components, opening the way to the experimental detection of many-body nonlocality, for instance with atomic ensembles.
In this talk we discuss a model consisting of n spin-1/2 particles with nearest-neighbor interactions moving on a 2D lattice wrapped around a torus of depth D. We consider two questions: a time for finishing computation for one qubit and a time for finishing computation for the whole string of n qubits. We investigate the dependence on n and D of the time interval T such that the computation of one qubit or the whole string is finished in a random time in this interval T.
The Solvay Institutes, as part of a regular series of colloquia, have scheduled a talk by François Englert, recipient of the 2013 Nobel Prize in physics. Luckily, this presentation will be held during our meeting, and we have made sure to free our schedule around the hour-long session so that you can attend the event.
The colloquium, which is free and open to everyone, will be held on the Plaine campus, located a fifteen minute walk from the Solbosch campus. You will find it on the map.
The abstract and precise location of the talk can be found on the announcement (PDF).