QUROPE Quantum Information Processing and Communication in Europe

Theory of entanglement

Secret correlations are an important resource already in classical cryptography where, for perfect secrecy, sender and receiver hold two identical and therefore perfectly correlated code-books whose contents are only known to them. Such secret correlations can neither be created nor enhanced by public discussion. Entanglement represents a novel and particularly strong form of such secret correlations. Therefore, entanglement is a key resource in quantum information science. Its role as a resource becomes even clearer when one is considering a communication scenario between distant laboratories. Then, experimental capabilities are constrained to local operations and classical communication (LOCC) as opposed to general non-local quantum operations affecting both laboratories. This is an important setting in quantum communication but also distributed quantum computation and general quantum manipulations. The resulting theory of entanglement aims to answer three basic questions.

Firstly, we wish to characterize and verify entangled resources to be able to decide, ideally in an efficient way, when a particular state that has been created in an experimental set-up or a theoretical consideration contains the precious entanglement resource. While the problem of entanglement detection has been shown to be hard, there exist numerical techniques that work well in many situations. For the experimental verification of this resource, the tool of entanglement witnesses allows to detect entanglement with local measurements only, and thus is easily implementable with present technology. Secondly, we wish to determine how entangled state may be manipulated under LOCC. In many situations an experimental setting will yield a certain type of entangled state that may suffer certain deficiencies. It may not be the correct type of state or it may have suffered errors due to experimental imperfections and be entangled. Once characterization methods have determined that the resulting state contains entanglement one can then aim to transform the initial state into the desired final state. Thirdly, it will be important to quantify the efficiency of all the processes and procedures as well as the entanglement resources that have been identified in the above two areas of research. If we have found entanglement in a state, then one will need to know how much of it there is.

Considerable progress in this area has been made in recent years, in particular in the case of bi-partite entanglement, but we are still far away from a comprehensive understanding of this key resource for quantum information processing. Research in this area will continue to play a central role in the field, and we expect that an increasing effort will be undertaken towards the classification and quantification of entanglement in multi-party entangled states. It is worth pointing out that insights in the theory of entanglement are not only important the field of QIS itself, but they have now reached the stage where they are being applied to other areas of physics (see Subsection 4.3.10).

Key references
[1] R. F. Werner, "Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model", Phys. Rev. A 40, 4277 (1989)
[2] M. Horodecki, P. Horodecki and R. Horodecki, "Separability of mixed states: necessary and sufficient conditions", Phys. Lett. A 1, 223 (1996)
[3] C. H. Bennett, H. J. Bernstein, S. Popescu and B. Schumacher, "Concentrating partial entanglement by local operations", Phys. Rev. A 53, 2046 (1996)
[4] V. Vedral and M. B. Plenio, "Entanglement measures and purification procedures", Phys. Rev. A 57, 1619 (1998)
[5] M. A. Nielsen, "Conditions for a class of entanglement transformations", Phys. Rev. Lett. 83, 436 (1999)
[6] M. Bourennane, M. Eibl, C. Kurtsiefer, S. Gaertner, H. Weinfurter, O. Guehne, P. Hyllus, D. Bruss, M. Lewenstein, and A. Sanpera, “Experimental detection of multipartite entanglement using witness operators”, Phys. Rev. Lett. 92, 087902 (2004)
[7] M. Horodecki, J. Oppenheim, and A. Winter, "Partial information can be negative”, Nature 436, 676 (2005)
[8] L. Gurvits, "Quantum matching theory (with new complexity theoretic, combinatorial and topological insights on the nature of the quantum entanglement)", arXiv:quant-ph/0201022.
[9] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, "Distinguishing separable and entangled states", Phys. Rev. Lett. 88, 187904 (2002)
[10] Recent tutorial reviews include M. B. Plenio and S. Virmani, “An introduction to entanglement measures”, Quant. Inf. Comp. 7, 1 (2007); R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, “Quantum entanglement”, Rev. Mod. Phys. 81, 865 (2009)

Multi-party entanglement and applications

Research on multi-particle entanglement is on the one hand expected to be focused on novel protocols for quantum information processing in the multi-partite setting. Entanglement in quantum systems embodying more than two constituents is fundamentally different from two-party entanglement, allowing for novel applications. This work on novel protocols includes work on instances of secret sharing or multi-partite fingerprinting. Notably, such multi-partite fingerprinting schemes would allow for the determination whether a number of databases are identical with little resources.

For quantum computation purposes it seems a major milestone to develop computation schemes that require minimal local control over interactions, such as in novel measurement-based computation schemes using multi-particle entangled resources as in cluster-state based approaches or in linear optics quantum computation. Alternatively, quantum cellular-automata based approaches may offer the potential of implementing quantum computation with little requirements of local control. Research work towards a complete understanding of the classification and quantification of multi-particle entanglement is expected to support such work, notably using methods from convex and global optimization, which give rise to novel methods for classification and quantification of entanglement. Laboratory quantum states such as random states or graph states as generalizations of cluster states may facilitate such studies.

On the other hand, there are good reasons to believe that a refined picture of criticality and phase transitions can be reached with the help of tools coming from the theory of entanglement. These ideas help in devising new simulation methods of ground states of many-body Hamiltonians in solid state physics (and many-body quantum systems in general). Finally, studies seem to indicate that questions in quantum field theory may become significantly more accessible using methods from entanglement theory (see also section 4.3.10)

Key references
[1] N. Linden, S. Popescu, B. Schumacher, and M. Westmoreland, "Reversibility of local transformations of multiparticle entanglement", quant-ph/9912039
[2] W. Duer, G. Vidal, and J. I. Cirac, "Three qubits can be entangled in two inequivalent ways", Phys. Rev. A 62, 062314 (2000)
[3] V. Coffman, J. Kundu, and W. K. Wootters, ``Distributed entanglement'', Phys. Rev. A 61, 052306 (2000)
[4] C. H. Bennett, S. Popescu, D. Rohrlich, J. A. Smolin, and A. V. Thapliyal, "Exact and asymptotic measures of multipartite pure state entanglement", Phys. Rev. A 63, 012307 (2001)
[5] A. Acin, D. Bruss, M. Lewenstein, and A. Sanpera, "Classification of mixed three-qubit states", Phys. Rev. Lett. 87, 040401 (2001)
[6] M. Hein, J. Eisert, and H.-J. Briegel, "Multi-party entanglement in graph states", Phys. Rev. A 69, 062311 (2004)
[7] B. Kraus, "Local unitary equivalence of multipartite pure states", Phys. Rev. Lett. 104, 020504 (2010)

Device independent certification of security in quantum information

Device independent quantum information processing represents a novel approach in which the goal is to design information protocols whose performance is independent of the internal working of the devices used in the implementation. The new framework exploits the non-local correlations exhibited by local measurements on entangled quantum particles, which certify the quantumness of the underlying state and measurements. That is the quantumness is certified by the violation of a Bell inequality.

This approach allows a qualitative increase of the security of quantum cryptography: QKD becomes secure even if the source of entangled states is not controlled and/or the measurement devices unknown. It also allows the generation and quantification of certified quantum randomness. The same basic philosophy can be applied to "self testing of quantum computers": by using quantum non locality one can test (in polynomial time) that a quantum computer indeed operates as it should, without the need to model how individual gates act, or the need to carry out the full tomography of the whole computer. Finally, these techniques may also find an application in estimation problems, as they allow estimating interesting quantum properties of an unknown system only from the observed measurement statistics.

From a theoretical point of view, the main goal is to understand the possibilities and limitations of this new approach. From a more practical point of view, a major theoretical and experimental challenge is to make these proposals practical. On the experimental side by realising long distance Bell inequality violation with the detection loophole closed. On the theoretical side by improving the existing protocols, or by relaxing some of the assumptions.

Key references
[1] D. Mayers and A. Yao, "Self testing quantum apparatus", Quantum Inform. Comput. 4, 273 (2004)
[2] J. Barrett, L. Hardy, and A. Kent, "No Signalling and Quantum Key Distribution", Phys. Rev. Lett. 95, 010503 (2005)
[3] A. Acin, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, "Device-independent security of quantum cryptography against collective attacks", Phys. Rev. Lett. 98, 230501 (2007)
[4] L. Masanes, S. Pironio, and A. Acin, "Secure device-independent quantum key distribution with causally independent measurement devices", Nature Comm. 2, 238 (2011)
[5] S. Pironio {\sl et al.}, "Random numbers certified by Bell's theorem", Nature 464, 1021 (2010)
[6] R. Colbeck and A. Kent, "Private randomness expansion with untrusted devices", Journal of Physics A 44, 095305 (2011)
[7] M. Hendrych {\sl et al.}, "Experimental estimation of the dimension of classical and quantum systems", Nature Phys. 8, 588 (2012)
[8] J. Ahrens, P. Badziag, A. Cabello, and M. Bourennane, "Experimental device-independent tests of classical and quantum dimensions", Nature Phys. 8, 592 (2012)
[9] N. Gisin, S. Pironio, and N. Sangouard, "Proposal for implementing device-independent quantum key distribution based on a heralded qubit amplification", Phys. Rev. Lett. 105, 070501 (2010)

Noisy communication channels

The proper understanding of the capacities of quantum communication channels is at the heart of the study of quantum communication tasks. Of particular importance are the transmission of classical or quantum information, or establishing secret keys. The general framework for distilling classical keys from quantum states have been also established, opening the possibility of secure communication on extremely noisy channels. But it is also known that one can use noise and perfect side communication to implement other cryptographic primitives like bit commitment and oblivious transfer. Channel capacities are of central interest in several different settings, being reflected notably by the classical capacity of quantum channels, quantum capacities, and entanglement-assisted capacities.

The central question is essentially what resources are required for transmitting classical or quantum information using quantum channels, such as optical fibers in a practical realization. A problem that was left open until recently was whether an increased capacity can be obtained by employing entangled signal states (multiple uses) as opposed to single uses of the channel. This problem is widely known as the additivity problem for the Holevo capacity or - as it turned out, equivalently, the additivity problem for the minimum output entropy. This problem could recently be solved in seminal work, in that it turned out that entangled inputs indeed do help. Similarly, it has been shown theoretically that two quantum channels, each with a quantum capacity of zero, can have a non-zero capacity when used together. The key problem of identifying the classical information capacity for Gaussian channels - in the context of the promising field of continuous-variable quantum information, with practical importance in quantum communication with fibers - is still open, despite recent progress. These findings open up new exciting questions about the role of entanglement in quantum communication. Also, the exact relationship between entanglement and the correlations useful for establishing secret keys is not yet entirely understood.

Finally, it is to be expected that more problems, as well as new perspectives, will arise when one considers multi-user channels, i.e. with more than one sender/receiver. While single-sender-receiver settings serve well to study bipartite correlations, such problems have an immediate impact on understanding multi-partite correlations and their role in quantum communication via noisy channels. Also, quantum analogues of certain basic classical network theory primitives have been identified, and the evidence for new non-classical features, such as negative partial information established. Further investigations will be needed to identify differences and similarities in the classical and quantum network theories.

Key references
[1] C. H. Bennett, G. Brassard, C. Crépeau, and M.-H. Skubiszewska, "Practical quantum oblivious transfer", Lecture Notes in Computer Science 576, 351 (1991)
[2] S. Holevo, "The capacity of the quantum channel with general signal states", IEEE Trans. Inf. Theory 44, 269 (1998)
[3] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, "Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem", Phys. Rev. Lett. 83, 3081 (1999)
[4] P. W. Shor, "Equivalence of additivity questions in quantum information theory", Commun. Math. Phys. 246, 453 (2004)
[5] K. Horodecki, M. Horodecki, P. Horodecki, and J. Oppenheim “Secure key from bound entanglement”, Phys. Rev. Lett. 94, 160502 (2005)
[6] P. Hayden and A. Winter, "Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1", Comm. Math. Phys. 284, 263 (2008)
[7] M. B. Hastings, "A counterexample to additivity of minimum output entropy", Nature Physics 5, 255 (2009)
[8] G. Smith and J. Yard, Science 321, 1812 (2008)

"Quantum proofs" for classical problems

A very exciting aspect of theoretical work in QIS is the impact that it is beginning to make on other fields of science. In the case of classical computing such insights include the first exponential bounds on certain locally decodable codes, classical proof systems for lattice problems, bounds on the query complexity of local search problems, an efficient classical cryptographic scheme whose security is based on quantum considerations, and a quantum method to compute how many Toffoli gates are required to realize a reversible classical computation. The potential that QIS is offering for classical computing and mathematics may be understood by the following analogy. Real analysis is a very successful discipline but it contained a number of unsolved problems that were only solved by considering complex numbers, i.e. going to a larger space in which to describe the problem. By analogy we expect that moving from classical state space into the much larger quantum mechanical state space we will find novel approaches towards the solution of problems that ostensibly lie entirely within the classical realm.

For instance, a 20-year old problem on the existence of no polynomial-size linear program whose associated polytope projects to the traveling salesman polytope was recently solved using techniques from one-way quantum communication protocols. In this sense, quantum information theory offers novel proof tools for "quantum proofs" for classical problems, hence quantum information theory having a significant impact outside quantum theory. Similarly, recent ideas from quantum state tomography developing a notion of quantum compressed sensing are now routinely used in classical compressed sensing and the theory of image processing.

The entanglement between two systems cannot be shared with many others, a principle called monogamy: this leads to a fruitful relationship between entanglement theory and classical cryptography, and in particular between entanglement distillation and the classical key agreement scenario. Since the two schemes shares similar objects, quantities and relations, it is expected that the parallel growth of these domains will lead to a deeper understanding of both of them. For instance, it has been conjectured the existence of a classical cryptographic analog of bound entanglement, named bound information. While its existence remains unproven for two parties, a proof has been obtained in a multipartite scenario.

Key references
[1] I. Kerenidis and R. de Wolf, "Exponential lower bound for 2-query locally decodable codes via a quantum argument", quant-ph/0208062
[2] S. Popescu, B. Groisman and S. Massar, "Lower bound on the number of Toffoli gates in a classical reversible circuit through quantum information concept", quant-ph/0407035
[3] N. Gisin and S. Wolf “Linking classical and quantum key agreement: Is There “Bound information”?” in Proceedings of CRYPTO 2000, Lecture Notes in Computer Science vol. 18889, pp. 482-500, Springer (2000)
[4] A. Acin, J. I. Cirac, and Ll. Masanes “Multipartite bound information exists and can be activated”, Phys. Rev. Lett. 92, 107903 (2004)
[5] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, "Quantum state tomography via compressed sensing", arXiv:0909.3304 [quant-ph]; D. Gross, "Recovering low-rank matrices from few coefficients in any basis", arXiv:0910.1879 [quant-ph]
[6] A. Drucker and R. de Wolf, "Quantum proofs for classical problems", arXiv:0910.3376 [quant-ph]
[7] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf, "Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds", Proc. 43rd ACM Symposium on Theory of Computing (STOC), 95 (2012)