Abstracts

Atul Singh Arora (Bruxelles)

Title: Quantum weak coin flipping beyond bias 1/6

Abstract:

Coin flipping is a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. We say that a coin flipping protocol has bais ε if neither player can force the outcome towards his/her preferred value with a probability more than ½+ε. It has been shown that weak coin flipping can be achieved with an arbitrarily small bias (near perfect) but the best known explicit protocol has bais 1/6. We have constructed a new framework using which we can construct explicit protocols with bias up to 1/10. The framework must be supplemented by a systematic method for constructing the unitaries involved in better protocols. We have proposed such a method based on an algorithm which seems to work numerically in all the cases we have tried, including some moves used in bias 1/18 protocols, and we are currently working on proving its correctness for all possible moves.

Joint work with Jérémie Roland and Stephan Weis

Alexander Belov (Riga)

Chris Cade (Bristol)

Title: Post-selected classical query complexity

Abstract:

The precise relationship between post-selected classical and post-selected quantum computation is an open problem in complexity theory, and lies at the heart of many results in the area of quantum computational supremacy. In this talk, we consider the difference in computational power of classical and quantum post-selection in the query setting. We define post-selected classical query algorithms, and relate them to rational approximations of Boolean functions; in particular, by showing that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations to the Majority function. 

Shantanav Chakraborty (Bruxelles)

Title: Finding a marked node on any graph by continuous time quantum walk

Abstract:

We provide a new spatial search algorithm by continuous-time quantum walk which can find a marked node on any ergodic, reversible Markov chain P, in a time that is quadratically faster than the corresponding classical random walk on P. In the scenario where multiple nodes are marked, the running time of our algorithm scales as the square root of a quantity known as the extended hitting time. This solves an open problem concerning the difference between the running time of spatial search by discrete-time and continuous time quantum walk. We also show that the widely used Childs and Goldstone algorithm for spatial search by continuous-time quantum walk is quite restrictive: we identify limitations in its applicability whenever P is not state-transitive. We subsequently improve and extend this algorithm to be applicable for any P. Our generalizations imply that most hitherto published results on the performance of quantum spatial search in the Childs and Goldstone framework on specific graphs are particular cases of our result. However, we prove that the running time of the Childs and Goldstone algorithm and its subsequent improvement is suboptimal: our spatial search algorithm outperforms it. Our results can be adapted to a number of Markov chain-based quantum algorithms and will lead to exploring other connections between discrete-time and continuous-time quantum walks.

Joint work with Leonardo Novo and Jérémie Roland

Matthias Christandl (Copenhagen)

Tensors: From Entanglement to Computational Complexity

The quantum state of a system of k particles can be viewed as a tensor of order k. Local stochastic operations on a quantum state correspond to the application of linear maps to the indices of the corresponding tensor and are studied in entanglement theory and implemented in current quantum information science experiments.

Interestingly, the notion of tensor transformation is at the heart of the study of the computational complexity of algebraic problems such as the multiplication of matrices. Strassen’s breakthrough algorithm for the multiplication of d-by-d matrices that runs faster than your standard d^3 high-school algorithm, spurred a whole development of tensor theory.

I will review these connections and present a new family of quantum information-inspired functionals that can serve as obstructions for asymptotic tensor transformations. The functionals are the first of their kind, thereby solving a problem of Strassen from 1986.

Eleni Diamanti (Sorbonne Université, invited talk)

Title: Demonstrating quantum advantage in security and efficiency with practical photonic systems

Abstract:

In this talk, we discuss the current landscape in quantum communication and cryptography, and focus in particular on recent photonic implementations, using encoding in discrete or continuous properties of light, of central quantum network protocols, enabling secret key distribution, verification of entangled resources and transactions of quantum money, with maximal security guarantees. We also describe current challenges in this field and our efforts towards the miniaturization of the developed photonic systems, their integration into telecommunication network infrastructures, including with satellite links, as well as the practical demonstration of novel protocols featuring a quantum advantage in communication efficiency for a wide range of useful tasks in a network environment. These advances enrich the resources and applications of the emerging quantum networks that will play a central role in the context of future quantum-safe communications.

João Fernando Doriguello (Bristol)

Title: Quantum sketching protocols for Hamming distance and beyond

Abstract:

In this work we use the concept of quantum fingerprinting to develop a quantum communication protocol in the simultaneous message passing model that calculates the Hamming distance between two n-bit strings up to relative error epsilon. The communication complexity of the protocol is poly(log(n)) qubits, while any classical protocol must communicate Omega(sqrt(n)) bits. Motivated by the relationship between Hamming distance and vertex distance in hypercubes, we apply the protocol to approximately calculate distances between vertices in graphs that can be embedded into a hypercube such that all distances are preserved up to a constant factor. This class includes all median graphs, a class which includes all trees. We call these graphs k-partial cubes and completely characterize them. Our protocol is efficient for k-partial cubes with low diameter.

Omar Fawzi (ENS Lyon, invited talk)

Title: Quantum de Finetti theorems with linear constraints

Abstract: 

de Finetti theorems relate permutation invariant probability distributions (or quantum states) to independent and identically distributed ones. In recent years, such theorems have found multiple applications in quantum information theory, cryptography and complexity. In this talk, I will review the standard quantum de Finetti theorems, give a new one that allows for linear constraints and show how it can be applied to obtain semidefinite programming hierarchies for channel coding.

András Gilyén (CWI)

Title: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Abstract: 

Quantum computing is powerful because unitary operators describing the time-evolution of a quantum system have exponential size in terms of the number of qubits present in the system. We develop a new “Singular value transformation” algorithm capable of harnessing this exponential advantage, that can apply polynomial transformations to the singular values of a block of a unitary, generalizing the qubitization results of Low and Chuang.

“Singular value transformation” is conceptually simple and efficient, and leads to a unified framework of quantum algorithms incorporating a variety of quantum speed-ups. We illustrate this by showing how it generalizes a number of prominent quantum algorithms, such as: optimal Hamiltonian simulation, implementing the Moore-Penrose pseudoinverse (i.e., the HHL algorithm) with exponential precision, fixed-point amplitude amplification, robust oblivious amplitude amplification, fast QMA amplification, fast quantum OR lemma, certain quantum walk results and several quantum machine learning algorithms.

The proposed quantum circuits have a very simple structure, often give rise to optimal algorithms and have appealing constant factors, while usually only using a constant number of ancilla qubits. We show that singular value transformation leads to novel algorithms as well, for example it enables one to efficiently implement a certain “non-commutative” measurement protocol, an exponentially improved fractional query algorithm for unitaries with a gapped spectrum, or quantum machine learning algorithms such as principal component regression.

In order to exploit the strengths of the presented method it is useful to know its limitations too, therefore we also prove a lower bound on the efficiency of singular value transformation, which often gives optimal bounds.

Yassin Hamoudi (Paris-Diderot)

Title: Quantum Chebyshev’s inequality and applications

Abstract:

We describe a new quantum paradigm, that we call Quantum Chebyshev’s inequality, to approximate with relative error the mean of any random variable with a number of quantum samples that is linear in the ratio of the square root of the variance to the mean. Classically the dependency is quadratic. To illustrate this method, we apply it to the approximation of the frequency moments F_k of order k > 2 in the multi-pass streaming model, and to the approximation of the number of edges and triangles in the quantum graph query access model. This new paradigm is based on a refinement of the Amplitude Estimation algorithm [BHMT02], and of previous quantum algorithms for the mean estimation problem. It is optimal and it subsumes a previous result of Montanaro [Mon15].

Joint work with Frédéric Magniez.

Iordanis Kerenidis (Paris-Diderot)

Title: Quantum Algorithms for Classification

Abstract:

We provide new quantum algorithms for supervised and unsupervised classification, one of the fundamental problem in Machine Learning, and analyse their accuracy and efficiency on real data. Joint work with Jonas Landman, Alessandro Luongo and Anupam Prakash

Simon Martiel (Atos)

Title: Meta-heuristics for quantum circuit optimization under realistic constraints

Abstract:

Quantum algorithm descriptions often assume the existence of a perfect (or at least error corrected) quantum information processor that is able to efficiently preform any universal set of gates.

The current state of the art of QIP is far from this theoretical assumptions. Currently available quantum processors are noisy and come with very constraining limitations, such as hardware gate sets with low expressivity and qubit connectivity.

In this talk, we will present a compilation suite combining the use of circuit transformation (via either pattern-based rewriting or SWAP gate insertion) guided by meta-heuristics.

We will show how to achieve interesting fidelity gains using simple metrics to guide the meta-heuristics.

Abel Molina (IQC)

Title: Revisiting the simulation of quantum Turing machines by quantum circuits

Abstract: 

Yao (1993) proved that quantum Turing machines and uniformly generated quantum circuits are polynomially equivalent

computational models: t >= n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated

family of quantum circuits with size quadratic in t, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t, rather than quadratic depth, and can be extended to variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of a method of Arrighi, Nesme, and Werner (2011) that allows for the localization of causal unitary evolutions.

María Naya-Plasencia (INRIA, invited talk)

Title: New Results on Symmetric Quantum Cryptanalysis

Abstract: 

The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and A. Schrottenloher), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and A. Schrottenloher). We will discuss some implications of these results in quantum-safe symmetric cryptography.

Ashwin Nayak (IQC)

Title: Online Learning of Quantum States

Abstract:

Suppose we have many copies of an unknown n-qubit state rho. We measure some copies of rho using a known two-outcome measurement E_1, then other copies using a measurement E_2, and so on. At each stage t, we generate a current hypothesis sigma_t about the state rho, using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that Tr(E_i sigma_{i-1}) differs from Tr(E_i rho) by more than epsilon at most O(n/epsilon^2) times. Even in the “non-realizable” setting—where there could be arbitrary noise in the measurement outcomes—we show how to output hypothesis states that do significantly worse than the best possible states at most O(sqrt(Tn)) times on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online setting. This setting more closely captures ground reality in experimental state tomography, and what more, has found application in the seemingly unrelated task of *shadow tomography*.

Joint work with Scott Aaronson, Xinyi Chen, Elad Hazan, and Satyen Kale.

Sergii Strelchuk (Cambridge)

Title: Classical and quantum features of the Schur transform for information processing

Abstract: 

In the last 15 years, the Schur Transform has found applications in an astounding number of quantum information processing tasks. In this talk, I will provide an introduction to the Schur Transform and survey its recent applications. I will further show that most of its widely-believed quantum features are classically tractable: the outputs of Schur sampling circuits are unconditionally strongly simulatable and weakly simulatable under certain sparsity assumptions.

David Touchette (IQC)

Title: Information Flow in Quantum Communication Protocols: the Cost of Forgetting

Abstract: 

In the basic communication complexity setup, Alice and Bob are given classical inputs x and y, respectively, and they want to compute a bipartite function f(x, y) while minimizing the amount of communication they must exchange. In the closely related information complexity setting, we are instead interested in the least amount of information that Alice and Bob must leak to each other about their respective inputs in order to compute the function f(x, y). This information complexity paradigm has proven to be a powerful tool for obtaining communication complexity lower bounds in both the classical and quantum settings.

In quantum protocols, it is possible for Alice and Bob to forget information they have learned about each other’s classical input. In this talk, we explore the many consequences of this ability of quantum protocols to forget information for defining a quantum notion of information cost.

Based on joint work with Mathieu Lauriere

Jevgēņijs Vihrovs (Riga)

Title: Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

Abstract:

We study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from 0n to 1n in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time \tilde{O}(1.817^n). The technique combines Grover’s search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time \tilde{O}(1.817^n), and graph bandwidth in time \tilde{O}(2.946^n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time \tilde{O}(1.728^n). 

Joint work with Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, arXiv:1807.05209