Academic CentreYear 1
1. Learning graphs and quantum walks.
Learning graphs have been a powerful tool for designing new quantum algorithms and have lead to new quantum algorithms for a variety of problems. However, some of the learning graph based algorithms (in particular, the quantum algorithm for the $k$-distinctness problem) are efficient in terms of the number of queries (accesses to input data) but are not efficient with respect to the overall computation time.
We have been able to overcome this problem, developing two time-efficient quantum based algorithms for the problem of 3-distinctness (finding 3 equal elements in an array). The first algorithm is based on a new connection with the electric networks. We design a form of quantum walk in which algorithm's quantum state corresponds to an electric flow on a certain network. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
2. Hidden shift problem.
We have investigated the quantum query complexity of the Boolean hidden shift problem. We demonstrated that the easiest instances correspond to bent functions---an exact one-query algorithm exists if and only if the function is bent. We partially characterized the hardest instances, which include delta functions. Moreover, we showed that the problem is easy for random functions, since two queries suffice.
3. Property testing.
We have completed a survey on a new research area, quantum property testing. Property testing studies very fast algorithms for determining whether the input data have a certain property or are far from having it. Property testing is well studied in conventional computer science and has found many applications there. In contrast, quantum property testing is much less studied.
We survey the known results on quantum property testing in three broad directions:
- quantum testers for properties of classical objects, where quantum testers can be much (sometimes exponentially) more efficient than classical testers;
- classical testers of quantum objects, where the goal is to determine properties of quantum states or operations based on classical input-output behaviour, a scenario that is relevant from experimental perspective;
- quantum testers for properties of quantum objects such as states or operations, where bounds on testing various natural properties are surveyed.
The survey also highlights connections to other areas of quantum information theory such as complexity theory. We expect that our survey will serve as a systematic guide for future research in this area.
WP2 General Properties of Quantum Algorithms
1. Exact quantum algorithms.
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). Designing exact quantum algorithms is substantially more difficult than usual bounded error algorithms which may output an incorrect answer with a small probability. Until recently, the biggest advantage for exact quantum algorithms was just a factor of 2: it was known that parity of N bits can be computed by an exact quantum algorithm using N/2 queries to the input bits, whereas classical algorithms require N queries. We present the first example of a total Boolean function for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675...}) queries. This solves an open problem that has been well known in the quantum algorithms community for at least 10 years.
2. Quantum Attacks on Classical Proof Systems.
For many classically secure protocols it is not clear if they also resist quantum attacks because the classical proof techniques often cannot be applied in the quantum world. This raises the question whether the known proof techniques are insufficient or the protocols themselves are quantum insecure. Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding can be handled by known techniques, yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. To show these results, we develop a general technique that allows an adversary to find one value satisfying a given predicate but not two.
3. Adversary lower bounds.
Adversary method is a very powerful mathematical tool that can be used (in principle) to prove tight lower bounds on query complexity of quantum algorithms. In practice, however, it is often hard to construct a solution to this bound that would be close to the optimal. Collision and Set Equality are two problems for which no such solution is known. Furthermore, a weaker (but simpler to use) form of the adversary method with only positive weights is not strong enough for obtaining a solution for these problems. Even though tight bounds are known due to an alternative (polynomial) method, all attempts of reproducing the same bounds with the adversary method have been futile. We have overcome these limitations and proved tight lower bounds on the quantum query complexity of the Collision and Set Equality problems, thus extending the range of applications of the adversary method.
WP3 Algorithms in Quantum Communication
1. Optimal device-independent randomness evaluation.
We show how to take into account the full information about the probability distributions characterizing the measurement outcomes of a Bell test in a systematic manner in order to optimally evaluate the randomness that can be certified from non-local correlations. We further determine the optimal Bell inequality for certifying the maximal amount of randomness from a given set of non-local correlations.
2. Information versus communication via non-local games.
In a collaboration between Paris and ULB groups of our project, we showed that all known optimal communication protocols can be compressed to their information content. The result uses a new connection between lower bound techniques for communication complexity and the efficiency of non-local games where the players can either output a value or abort. 3. Experimental implementation of quantum coin flipping.
We have experimentally implemented a quantum protocol for performing a coin flip by two parties which do not trust one another.
The protocol that we implemented performs strictly better than classically possible over a distance suitable for communication over metropolitan area optical networks. The implementation is based on a practical plug and play system, designed for quantum key distribution.
We also show how to combine our protocol with coin flipping protocols that are almost perfectly secure against bounded adversaries, hence enhancing them with a level of information-theoretic security.
WP4 Quantum Information in Computer Science and Physical Systems
1. Circuit-to-Hamiltonian translations.
While computer scientists like to think of a quantum computer as a circuit of elementary gates, from the physics perspective the primary object is the Hamiltonian. This matrix describes the different forces at work in the system, and corresponds to the observable for the total energy in the system. Translations between the two views are important. The standard circuit-to-Hamiltonian translation due to Feynman and (subsequently) Kitaev has been a fundamental tool in the study of complexity of physical systems, with many applications: it allows one to construct a universal adiabatic computation, universal quantum random walks, as well as derive results in quantum complexity theory. It crucially involves a quantum register for a clock. We have formalized a new circuit-to-Hamiltonian translation which assigns a clock to each interacting qubit, so now there are many local clocks instead of one global one. They used this to solve a long-standing open problem, namely the mathematical analysis of the spectral gap of the fermionic ground-state computation introduced by Mizel et al. in 2001.
Year 2
WP1 New ideas for quantum algorithms
Query model studies the complexity of computing in terms of the number of access to input data (queries). It provides a useful approach to study the power of quantum computation, since many of the known quantum algorithms can be described in this model.
It is known that quantum query complexity is characterized in terms of a semide nite program (SDP), the Adversary SDP. This means that one can obtain lower bounds for speci c problems by solving this semidefi nite program and quantum algorithms for these problems by solving its dual. This idea is increasingly used for designing new quantum algorithms. Here are some of our contributions in this direction. 1. Bounds on parallel quantum walk algorithms.
We studied the complexity of quantum query algorithms that make several queries in parallel in each timestep. We obtained tight bounds for a number of problems, speci cally for element distinctness ( finding two equal elements in an array) and for the k-SUM problem (determining whether an array of numbers contains k numbers whose sum is equal to a given number; this problem is signi ficant for cryptoanalysis). The upper bounds are obtained by parallelizing the known quantum algorithms for those problems which are based on the use of quantum walks (quantum counterparts of random walks), and the lower bounds are based on a relatively small modi fication of the adversary lower bound method, combined with recent results of Belovs et al. reported last year on learning graphs (a new approach for analyzing the Adversary SDP). This paper connects two research directions of our project: quantum walks and the learning graph model. 2. New quantum algorithm for monotonicity testing.
While the first SDP-based quantum algorithms were designed using the framework of learning graphs, in our most recent work, we have started to design solutions of the dual SDP directly, without any intermediate framework. The result is a new quantum algorithm for monotonicity testing (the problem of testing whether a Boolean function is monotonic or far from monotonic) which is faster than any classical algorithm for the same problem. This links together two tasks of our project: finding new uses for the learning graph/adversary bound method and fi nding new quantum algorithms in the area of property testing.
Besides these contributions, we have also made progress in the areas of quantum algorithms for hidden subgroup problems, quantum-walk based algorithms, and adiabatic quantum computation. WP2 General Properties of Quantum Algorithms The three most important achievements of our project in this direction are: 1. Classical simulations of matchgate circuits.
The theory of matchgate computations was introduced by Valiant and used to provide a striking new class of efficient classical algorithms for a variety of computational tasks. We have obtained a complete characterization of 2-input and 2-output matchgates, and we give an efficient simulation for all cases in Valiant's simulation theorem. This extends previous results on efficient classical simulation of non-interacting fermions (because operations on non-interacting fermions can be described in the matchgate formalism). 2. Separating quantum from classical query complexity.
We have obtained further results on the number of queries to the input data required for performing certain computational tasks classically and quantumly. In particular, we showed that if a property of input data of size n can be computed with k quantum queries, it can be also computed with O(n1-1/2k) queries classically. We constructed a candidate problem for which we conjecture that this bound is optimal. As a step towards resolving this conjecture, we were able to establish a somewhat weaker lower bound. We have also considered the task of sampling from a probability distribution that depends on the input data and showed that a certain problem of this type can be solved quantumly with just one query but requires Ω(n/log n) queries classically. This gap between quantum and classical computation is even bigger than the gaps that we found for the task of computing functions. 3. Extensions of the adversary method.
The quantum adversary bound is a powerful tool for studying limitations of quantum query algorithms. We have analyzed the extent to which it can be further generalized. We obtained a version of the adversary bound for arbitrary unitary input oracles as well as for the problem of implementing arbitrary unitary transformations. Using this construction, we also obtained lower bounds on the quantum query complexity of functions and relations with general input oracles. WP3 Algorithms in Quantum Communication We highlight two results in quantum communication. 1. Quantum communication complexity advantage implies violation of a Bell inequality.
In a paper by Buhrman et al., we obtained a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol o ering a (suf ciently large) quantum advantage in communication complexity, there exists a way of obtaining measurement statistics which violate some Bell inequality. The main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs. 2. Nonlocality and conflicting interest games.
In a paper by Pappa et al., we studied nonlocality and conflicting interest games. Nonlocality enables two parties to win speci fic games with probabilities strictly higher than allowed by any classical theory. Nevertheless, all known such examples consider games where the two parties have a common interest, since they jointly win or lose the game.
We asked the question: do the nonlocal features of quantum mechanics o er an advantage in a scenario where the two parties have conflicting interests? We answered this question in the 2 afirmative by presenting a simple conflicting interest game, where quantum strategies outperform classical ones. We also showed that our game has a fair quantum Nash equilibrium with higher payo ffs for both players than in any fair classical Nash equilibrium and demonstrated how to play this game using a commercial entangled photon source, showing the quantum advantage experimentally. WP4 Quantum Information in Computer Science and Physical Systems In recent years, it has been discovered that the ideas of quantum information can be applied to other fi elds (both classical computer science and the study of quantum physical systems), often in unexpected ways. We highlight two such results from our project. 1. Quantum algorithms with postselection versus rational functions.
Ecient quantum query algorithms induce low-degree polynomials. This well-known connection between algorithmic and algebraic concepts has been very fruitful in the past 15 years in two directions: proving limitations on quantum algorithms using algebraic tools (e.g., degree lower bounds) and constructing low-degree polynomials using ecient quantum algorithms.
Sometimes, one onsiders quantum algorithms that have the added power of postselection. This allows the algorithm to pick a speci fic measurement outcome instead of having the usual probabilistic collapse to a random outcome. Nature does not allow us to postselect, but this computational model is still interesting for various reasons. In we obtained a very tight analogue: the optimal complexity of quantum algorithms with postselection that compute a certain function, is essentially equal to the minimal degree of a rational function (i.e., ratio of two polynomials) that approximates this function. This connection is much tighter than the one for regular quantum algorithms, and we hope it will be as fruitful. 2.Preparing ground states of speci c Hamiltonians.
We have been studying the underlying structure of a wide range of states of physical systems, with the aim of understanding how these states can be realized on quantum computers. The central tool in that regard has been Projected Entangled Pair States (PEPS), which on the one hand provide a succinct description for general physical states of complex quantum systems, and on the other hand can be used to devise preparation procedures for such states based on the understanding of their underlying algebraic structure.
In [9] we studied the ability of PEPS to describe physical states of complex quantum system, such as ground states or thermal states. In particular, we showed that thermal states can be approximated eciently, i.e., with low bond dimension. We also developed a general PEPS-based scheme for preparing arbitrary topologically ordered states on a quantum computer.
It is known that quantum query complexity is characterized in terms of a semide nite program (SDP), the Adversary SDP. This means that one can obtain lower bounds for speci c problems by solving this semidefi nite program and quantum algorithms for these problems by solving its dual. This idea is increasingly used for designing new quantum algorithms. Here are some of our contributions in this direction. 1. Bounds on parallel quantum walk algorithms.
We studied the complexity of quantum query algorithms that make several queries in parallel in each timestep. We obtained tight bounds for a number of problems, speci cally for element distinctness ( finding two equal elements in an array) and for the k-SUM problem (determining whether an array of numbers contains k numbers whose sum is equal to a given number; this problem is signi ficant for cryptoanalysis). The upper bounds are obtained by parallelizing the known quantum algorithms for those problems which are based on the use of quantum walks (quantum counterparts of random walks), and the lower bounds are based on a relatively small modi fication of the adversary lower bound method, combined with recent results of Belovs et al. reported last year on learning graphs (a new approach for analyzing the Adversary SDP). This paper connects two research directions of our project: quantum walks and the learning graph model. 2. New quantum algorithm for monotonicity testing.
While the first SDP-based quantum algorithms were designed using the framework of learning graphs, in our most recent work, we have started to design solutions of the dual SDP directly, without any intermediate framework. The result is a new quantum algorithm for monotonicity testing (the problem of testing whether a Boolean function is monotonic or far from monotonic) which is faster than any classical algorithm for the same problem. This links together two tasks of our project: finding new uses for the learning graph/adversary bound method and fi nding new quantum algorithms in the area of property testing.
Besides these contributions, we have also made progress in the areas of quantum algorithms for hidden subgroup problems, quantum-walk based algorithms, and adiabatic quantum computation. WP2 General Properties of Quantum Algorithms The three most important achievements of our project in this direction are: 1. Classical simulations of matchgate circuits.
The theory of matchgate computations was introduced by Valiant and used to provide a striking new class of efficient classical algorithms for a variety of computational tasks. We have obtained a complete characterization of 2-input and 2-output matchgates, and we give an efficient simulation for all cases in Valiant's simulation theorem. This extends previous results on efficient classical simulation of non-interacting fermions (because operations on non-interacting fermions can be described in the matchgate formalism). 2. Separating quantum from classical query complexity.
We have obtained further results on the number of queries to the input data required for performing certain computational tasks classically and quantumly. In particular, we showed that if a property of input data of size n can be computed with k quantum queries, it can be also computed with O(n1-1/2k) queries classically. We constructed a candidate problem for which we conjecture that this bound is optimal. As a step towards resolving this conjecture, we were able to establish a somewhat weaker lower bound. We have also considered the task of sampling from a probability distribution that depends on the input data and showed that a certain problem of this type can be solved quantumly with just one query but requires Ω(n/log n) queries classically. This gap between quantum and classical computation is even bigger than the gaps that we found for the task of computing functions. 3. Extensions of the adversary method.
The quantum adversary bound is a powerful tool for studying limitations of quantum query algorithms. We have analyzed the extent to which it can be further generalized. We obtained a version of the adversary bound for arbitrary unitary input oracles as well as for the problem of implementing arbitrary unitary transformations. Using this construction, we also obtained lower bounds on the quantum query complexity of functions and relations with general input oracles. WP3 Algorithms in Quantum Communication We highlight two results in quantum communication. 1. Quantum communication complexity advantage implies violation of a Bell inequality.
In a paper by Buhrman et al., we obtained a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol o ering a (suf ciently large) quantum advantage in communication complexity, there exists a way of obtaining measurement statistics which violate some Bell inequality. The main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs. 2. Nonlocality and conflicting interest games.
In a paper by Pappa et al., we studied nonlocality and conflicting interest games. Nonlocality enables two parties to win speci fic games with probabilities strictly higher than allowed by any classical theory. Nevertheless, all known such examples consider games where the two parties have a common interest, since they jointly win or lose the game.
We asked the question: do the nonlocal features of quantum mechanics o er an advantage in a scenario where the two parties have conflicting interests? We answered this question in the 2 afirmative by presenting a simple conflicting interest game, where quantum strategies outperform classical ones. We also showed that our game has a fair quantum Nash equilibrium with higher payo ffs for both players than in any fair classical Nash equilibrium and demonstrated how to play this game using a commercial entangled photon source, showing the quantum advantage experimentally. WP4 Quantum Information in Computer Science and Physical Systems In recent years, it has been discovered that the ideas of quantum information can be applied to other fi elds (both classical computer science and the study of quantum physical systems), often in unexpected ways. We highlight two such results from our project. 1. Quantum algorithms with postselection versus rational functions.
Ecient quantum query algorithms induce low-degree polynomials. This well-known connection between algorithmic and algebraic concepts has been very fruitful in the past 15 years in two directions: proving limitations on quantum algorithms using algebraic tools (e.g., degree lower bounds) and constructing low-degree polynomials using ecient quantum algorithms.
Sometimes, one onsiders quantum algorithms that have the added power of postselection. This allows the algorithm to pick a speci fic measurement outcome instead of having the usual probabilistic collapse to a random outcome. Nature does not allow us to postselect, but this computational model is still interesting for various reasons. In we obtained a very tight analogue: the optimal complexity of quantum algorithms with postselection that compute a certain function, is essentially equal to the minimal degree of a rational function (i.e., ratio of two polynomials) that approximates this function. This connection is much tighter than the one for regular quantum algorithms, and we hope it will be as fruitful. 2.Preparing ground states of speci c Hamiltonians.
We have been studying the underlying structure of a wide range of states of physical systems, with the aim of understanding how these states can be realized on quantum computers. The central tool in that regard has been Projected Entangled Pair States (PEPS), which on the one hand provide a succinct description for general physical states of complex quantum systems, and on the other hand can be used to devise preparation procedures for such states based on the understanding of their underlying algebraic structure.
In [9] we studied the ability of PEPS to describe physical states of complex quantum system, such as ground states or thermal states. In particular, we showed that thermal states can be approximated eciently, i.e., with low bond dimension. We also developed a general PEPS-based scheme for preparing arbitrary topologically ordered states on a quantum computer.
Year 3
1. Spatial search by quantum walk is optimal for almost all graphs.
Random walks (or Markov chains) are a powerful technique to design classical algorithms. In particular, they can be used to solve various search problems by walking randomly on a graph until a marked vertex, encoding a solution to the problem, is found. Similarly, quantum walks proved to be a fruitful technique to design new quantum algorithms, and have been shown to provide quantum speedups for various search problems.
In one of our recent contributions, we have shown that search by a quantum walk gives a substantial speedup over classical search for a wide range of structures. Namely, O(√T) steps suffice for searching almost any graph with T vertices (in the Erdos-Renyi model of random graphs). This shows that a quantum advantage for search on graphs is very generic. The result also has applications to quantum communication: it can be used to design a protocol for quantum state transfer on a network with the corresponding interconnection graph.
2. Efficient quantum algorithms for (gapped) group testing and junta testing.
The complexity of quantum algorithms in the query model can be characterized in terms of a semidefinite program (SDP), the Adversary SDP. Solving this SDP gives a quantum lower bound, and the dual of this SDP can also be used to obtain a quantum algorithm with a complexity that matches the best lower bound up to a constant factor.
The first SDP-based quantum algorithms were designed using the framework of learning graphs, which allows one to design solutions to the dual adversary SDP in an intuitive way. The next step is to use the solutions of the Adversary SDP directly, without any simplifying framework.
We have used this approach to design a quantum algorithm for the junta testing problem, by first designing a set of matrices that constitute a solution to the Adversary SDP and then translating it into an efficient quantum algorithm. Our quantum algorithm quadratically improves over the query complexity of the previous best quantum junta tester, and is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with a quartic improvement over the query complexity of the best classical algorithm.
WP2 General Properties of Quantum Algorithms
1. Quantum computing in low-dimensional spin chains.
Local spin chains are sequences of quantum systems in which each one interacts only with its immediate neighbors (so-called local Hamiltonian interactions). They form an important bridge between quantum many-body physics and quantum computing, especially via their ground state energy properties.
We have developed a new approach to encoding quantum computation in such spin chains by introducing a novel hybrid classical-quantum model of computation---a so-called quantum Thue system, inspired by classical string rewriting systems. It allows quantum computation to be represented in a spin chain with translationally-invariant interactions, and of unprecedentedly low local dimension, improving in this regard on the previous best result by several orders of magnitude. Despite their consequent simplicity, such systems are also shown to retain a remarkable complexity feature, viz., estimating their ground state energy is hard for the class QMA-EXP (a quantum analogue of NP), strengthening a dramatic connection between computational hardness and physical properties of almost practicably implementable systems.
2. New developments on quantum and classical query complexity.
The query model of computation and the associated notion of query complexity has played a fundamental role in the development of quantum algorithms from the very first quantum algorithm of Deutsch et al. (for distinguishing balanced vs. constant functions), which was framed in this model. This model remains very important, and its study has been a significant mainstay throughout the course of our project.
In the past year, we have obtained a series of important new results for both quantum and classical query complexity. We have given the first example of a total function with a super-quadratic gap between its quantum and its classical deterministic query complexities. The same function is used to also refute a long-standing conjecture of Saks and Wigderson (from 1986) on classical query complexities. Furthermore, we have given the first example of a separation between zero-error randomized query complexity and bounded-error randomized query complexity.
WP3 Algorithms in Quantum Communication
1. Separations in communication complexity using cheat sheets and information complexity.
We have given the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power-2.5 gap. Their results are communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). The main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat-sheet framework to communication complexity.
2. Communication complexity and Bell inequalities.
We have designed new methods to construct Bell violations, given gaps between classical and quantum communication complexity. This includes the first general construction for any function that exhibits a more than quadratic gap between quantum and classical communication.
WP4 Quantum Information in Computer Science and Physical Systems
1.Quantum algorithms in expectation.
Making a connection with questions in classical combinatiorial optimization, we have introduced and studied quantum algorithms that compute or approximate a function f:{0,1}n →R+ ``in expectation.'' This means that for every input x, the expected value of the algorithm's output equals or approximates f(x). They exactly characterize the optimal quantum query complexity of such algorithms by an algebraic notion, namely the sum-of-squares degree of f. This is an unusual model of computation, which is interesting in its own right, but that is also justified by connections with various questions in mathematics and optimization. In particular, it sheds new light on combinatorial optimization by means of semidefinite programs (the Lasserre hierarchy as well as more general SDP extensions of polytopes) and on so-called Positivstellensatz proof systems.
2.Universal computation using time-independent Hamiltonian on a 2D grid.
We show how to perform universal Hamiltonian and adiabatic computation using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles, which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, which allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent two-qubit ZZ and XX+YY interactions on an (almost) planar grid. The dynamics and spectral properties of the effective Hamiltonian can be fully determined, as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian, called the space–time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, the construction is potentially realizable using superconducting or other solid-state qubits. Electrons (and holes) with spin moving over a 2D grid could form a direct fermionic realization of the model.