Randomness has established itself as a vital building block of information processing and represents an integral ingredient for practically any aspect in the field of information processing and technology. The principal objective of this project is to establish and evaluate the role played by randomness in quantum information processing.


We shall address the main difficulties that arise through the use of randomness, in particular the following:


  • the use of randomness as a theoretical tool to prove existence and properties of information processing applications;
  • the design of novel quantum information processing applications that exploit randomness;
  • the design and analysis of applications that work with real-world (that is, non-uniform) randomness;
  • the construction of design techniques that produce high-quality randomness, both from a computational and adversarial perspective; and, finally,
  • the use of randomness to analyze and improve the physical processes necessary for the design quantum communication and computation devices.


The consortium (composed of 8 research teams) aims to unite the forces of EU expertise in computer science, physics and mathematics to undertake a comprehensive study of randomness and quantum information within their research portfolio.


Summary of project progress for the 1st year:

WP1 – Novel mathematical and theoretical methods of randomness:


In the first year we developed a new algorithm to generate random points inside an arbitrary d–dimensional convex body with respect to the flat measure. The Markov operator, connected to this task, which acts on the probability measures, was analyzed. We showed that any initial measure converges exponentially to the uniform measure in terms of the dimension d. We also studied Hamiltonians subject to Wiener noise and proved bounds on the time for convergence to a unitary k-design and studied applications in thermalisation and decoupling.


Further, we developed protocols based on a recently discovered class of codes – called polar codes – that are capacity-achieving while being computationally efficient. In particular, we introduced explicit schemes based on the polarization phenomenon for the task of secret-key agreement from common information and one-way public communication as well as for the task of private channel coding. Our protocols are distinct from previously known schemes in that they combine two practically relevant properties: they achieve the ultimate rate defined with respect to a strong secrecy condition and their complexity is essentially linear in the blocklength. We also analyzed how much channel dependent classical polar codes are, which is related to the open question if polar codes are universal or not.


Finally, we introduced the concept of boundariness that captures the most efficient way of expressing a given element of a convex set as a probability mixture of its boundary elements. We showed that boundariness is intimately related to (semi)norms that provide an operational interpretation of this quantity.


WP2 – Applications of randomness:


The main achievement within this part of the project was the characterization of the quantum advantage for a class of symmetric XOR games of n players with yes/no valued questions. In this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant under permutations of players. The result is that for a random n-players symmetric XOR game the entangled value of the game is O((ln n)½/n¼), adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. This implies that the classical-quantum gap for a random game in this class is O((ln n) ½).


We also proposed proposed so-called non-local “identity games”, as a suitable framework to study Bell inequalities. Surprisingly, despite no-signaling, it was found that non-local quantum strategies beat classical ones in terms of winning probability for identity games originating from certain bipartite and multipartite functions. Moreover, for the majority of functions (chosen uniformly at random), access to general non-signaling resources boosts success probability by a factor of 2 in comparison with classical ones.


The paradigm of zero-error communication has proved to provide a range of interesting non-local games for which quantum advantage could be shown, and has given rise to a renewed interest in “quantum combinatorics”. We showed that with the quantum no-signalling correlation instead of entanglement, quantum channels have a zero-error capacity described by semidefinite programs; a most surprising corollary is that for classical confusability graphs, the no-signalling assisted zero-error capacity is precisely the famous Lovász number.
Boson Sampling is a model where a random unitary matrix defines a computational task that is conjectured easy for quantum computers but hard for classical ones. We contributed to understanding this gap better, by asking whether and in which sense a (classical) computer could even tell apart the output of a supposed Boson Sampler from a classical impostor. As a consequence, subsequent work has focused on partially certifying photonic devices such as random Boson Samplers and non-interacting boson systems.


Further, we addressed the following quantum query complexity problem: “Given a set of n unitary matrices and the promise that they satisfy one out of n! specific properties, find which property is satisfied?” It has been shown that the problem can be solved using O(n) queries by employing the “superposition of quantum orders”, whereas the best quantum algorithm with fixed order of quantum operations (quantum circuit) requires O(n2) queries. Furthermore, this work proposes an interferometric setup to implement such a superposition of the orders, and explores the possibility of a real application where the experimental procedure would require a random sampling among the set of quantum operations that satisfy certain properties.


WP3 – Extracting randomness:


We developed the first device-independent protocol for randomness amplification using a constant number of devices. The protocol involves eight devices, can amplify any non-deterministic source into a fully random source, tolerates a constant rate of error, and has its correctness based solely on the assumption of non-signalling between the devices. Further we showed how to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy source in a device independent setting. To do this we use Mermin devices that exhibit super-classical correlations. The protocol is robust and tolerates devices that malfunction with a probability dropping polynomially in n at the cost of a minor increase of the number of devices used.


We have developed a general framework to describe and quantify randomness from noisy devices and to determine the post-processing (hashing) that is necessary and sufficient to extract almost perfect true randomness. Compared to previous work on random number generators (RNGs), we take this noise into account as side information, which is necessary to meet the above definition of true randomness. We have applied the framework to a new QRNG planned by idQuantique, which is based on a matrix of photodetectors. Our analysis also demonstrated that the choice of the light source is crucial and ideally the source should emit single photons in a pure spatial state.


Further, we investigated the possibility of (quantum) key repeaters, in the light of the existence of private correlations that have no or little distillable entanglement. While entanglement can be “repeated” by distillation and swapping/teleportation, we give strong evidence that without free entanglement there is little hope for something similar: Indeed, the distillable key after a very general class of repeater protocols is shown to be constrained in a number of nontrivial ways, showing that there is no hope of extending the range of certain very popular bound entangled private states.


WP4 – Applications of randomness in quantum many-body systems:


We made a significant progress in the application of novel tools of randomness in quantum many-body physics. In particular, we related dynamical properties (a vanishing group velocity and the absence of transport) with entanglement properties of individual eigenvectors. Using Lieb-Robinson bounds and filter functions, we have proven rigorously under simple assumptions on the spectrum that if a system shows strong dynamical localisation, all of its many- body eigenvectors have clustering correlations. In one dimension this implies directly an entanglement area law, hence the eigenvectors can be approximated by matrix-product states.


Further, we have studied a specific source of randomness, a heat bath, and checked which state-to-state transformations on the system are possible when one uses the heat bath as a resource. We have obtained limitations for off-diagonal elements of states in the case when the energy of the total system is conserved. This work has been complemented by other work on thermal machines and heat baths as sources of randomness. Specifically, we were concerned with the impact of correlations to notions of work extraction in quantum thermodynamics, using correlated baths as sources of randomness. We solved the problem of the locality of temperature on an abstract level and applied to concrete systems, making no assumptions of translational invariance, and hence being directly applicable to random many-body Hamiltonians.


Impact of achieved results


Since the objectives of this project were inspired by needs of quantum technologies the achieved results have direct impact on their future development and innovations. In particular, the results on randomness extraction and quantum codes are crucial for following steps towards complete reliability of quantum communication, quantum key distribution protocols and quantum random number generators. The results on non-local quantum games have potential to design novel interesting communication protocols and investigation of randomness in many-body significantly contributes towards our understanding of quantum thermodynamics. All these areas of technology are expected to strongly influence the future of our society.


(Photo source: http://images.sciencedaily.com)