Akadēmiskais centrsYear 1-2
1. Span programs and learning graphs.
Aleksandrs Belovs (LU group) has introduced learning graphs, a completely new approach to designing quantum algorithms. This approach builds on the semi-definite programming (SDP) characterization of quantum algorithms but is more intuitive and easier to use than the SDP approach.
Learning graph is a graph whose vertices correspond to states of knowledge of a quantum algorithm (sets of variables known to the algorithm). We have used learning graphs to construct a faster quantum algorithm for finding triangles in graphs. This work has attracted considerable attention in the area of quantum computing and was selected for a presentation as a plenary talk at QIP 2012, the leading international conference on quantum information.
2. Hitting time of quantum walks.
Recently, quantum walks (quantum counterparts of random walks) have emerged as one of most useful methods for designing quantum algorithms. Many of their applications are based on the fact that quantum search algorithms based on quantum walks can find objects with certain properties quadratically faster than classical algorithms that use classical random walks.
Frederic Magniez and Miklos Santha (UPD group), together with collaborators from Rutgers University have designed new methods for converting random walks into quantum walks which are more robust than the previously known methods. This has lead to faster quantum algorithms for problems where the previous methods were insufficient (for example, for searching a 2-dimensional grid for one of several objects with a certain property).
3. Quantum algorithms for systems of linear equations.
Recently, Harrow et al. came up with a surprising quantum algorithm for solving systems of linear equations, in the case when the algorithm has to produce the solution of the system as a quantum state. Andris Ambainis (LU group) has improved the running time of this quantum algorithm from O(k2 log N) to O(k log3k log N). Our improved algorithm is based on a new generalization of quantum amplitude amplification. We expect that the new version of amplitude amplification will find many other applications in quantum algorithms.
4. Non-local games and quantum entanglement.
Non-local games provide a quantitative framework for studying quantum entanglement (correlations between two spatially separated parts of a quantum state) and the differences between quantum and classical world.
Recently, there has been interest in the question: can we use non-local games for testing dimensionality of quantum states? That is, is there a non-local game that is winnable with a certain probability only if the two players share a quantum state of dimension at least d? Jop Briet and Harry Buhrman (CWI group), together with a collaborator from Australia, have answered this question in affirmative, by showing that two-player nonlocal games involving binary answers are sufficient for this purpose. Our main result is proven using a new generalization of the Grothendieck’s inequality, a celebrated result in geometric functional analysis.
5. Device-independent quantum cryptography.
In the distrustful quantum cryptography model the parties have conflicting interests and do not trust one another. Nevertheless, they trust the quantum devices in their labs. The aim of the device-independent approach to cryptography is to do away with the latter assumption, and, consequently, significantly increase security.
It is an open question whether the scope of this approach also extends to protocols in the distrustful cryptography model, thereby rendering them ‘‘fully’’ distrustful. UPD and ULB groups have shown that for bit commitment—one of the most basic primitives within the model—the answer is positive.
6. Extractors against quantum storage.
Randomness extractor is a mathematical object that can be used to improve the quality of a sequence of random bits. One of applications for extractors is quantum cryptography where they are used to improve the security of the secret key generated by a quantum key distribution (QKD protocol).
Constructions of extractors have been studied in detail in classical computer science but QKD applications require a new type of extractor: an extractor against quantum storage. Avi Ben-Aroya and Amnon Ta-Shma (TAU group) have constructed an almost optimal extractor in this setting.
7. Classical applications of ideas from quantum information.
Ronald de Wolf (CWI), together with a collaborator from MIT, has found a new application of the connection between quantum algorithms and polynomials, by providing a new proof of Jackson’s theorem (a classical result in mathematical analysis).
Jackson’s theorem is a stronger version of Weierstrass’s theorem (which says that any continuous function f on a closed interval can be e-approximated by some polynomial p) which gives the optimal tradeoff between the degree of the polynomial p and a certain measure of smoothness of f. The new proof of Jackson’s theorem is based on optimal quantum algorithms for approximating the Hamming weight of n-bit inputs. Such algorithms, indirectly, induce the low-degree approximating polynomials that Jackson’s theorem claims.
Year 3
LU group has made a breakthrough on the subject of 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 coming up with the usual bounded error quantum algorithms (which may output an incorrect answer with a small probability). Until recently, the biggest advantage for exact quantum algorithms (over classical 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 about the values of input bits (and it requires N queries for classical algorithms).
We present the first example of a total Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N0.8675...) queries. This solves an open problem that has been well known in the quantum algorithms community for at least 10 years.
2. Space-efficient quantum algorithms.
There are many examples of quantum algorithms that are faster than conventional algorithms. In contrast, there has been no examples of quantum algorithms using less memory than classical algorithms.
TAU group provides the first such example, by showing that the inverse of a well--conditioned matrix can be approximated in quantum logspace with intermediate measurements. The currently best classical algorithm for the problem requires (log2 n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix and how to approximate the SVD decomposition of a matrix whose singular values are well separated.
3. Deeper understanding of quantum query algorithms.
We have introduced a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the location of possible certificates in the input string (and not the precise values of input variables). We have shown that a tight algorithm for all certificate structures is given by non-adaptive learning graphs. This provides a limit on the current quantum algorithms of this type for several problems (for example, the well known problem of finding triangles in graphs) and shows that, for further improvements on these problems, new ideas (which use something that is not captured by the certificate structure) are required.
4. Quantum non-locality and Banach spaces.
We have explored a deep connection between quantum non-locality and operators in Banach spaces. CWI group, with collaborators, studied a particular form of non-local games (three party XOR-games) in which several players have to come up with answers satisfying a certain property without communicating among themselves. We showed that, if players share an extended GHZ quantum state, this provides only a constant advantage over the case when they have no common quantum state. Via the connection to Banach spaces, this solves a 35 year old problem from Banach space theory. We also extended this result to clique-wise entanglement and applied it to multipartite quantum communication complexity.
5. Security of quantum key distribution.
Device-Independent Quantum Key Distribution (DIQKD) is a formalism that supersedes traditional quantum key distribution, as its security does not rely on any assumption about the internal working of the devices. This strong form of security is possible using only devices producing correlations that violate a Bell inequality. Full security proofs of DIQKD have been recently reported, but they tolerate zero or small amounts of noise and are restricted to protocols based on specific Bell inequalities. ULB and ICFO groups provide a security proof of DIQKD that is both more efficient and noise resistant, and also more general as it applies to protocols based on arbitrary Bell inequalities. Our proof requires the extra assumption that the adversary does not have a long-term quantum memory but this condition is not a limitation at present since the best existing quantum memories have very short coherence times.
6. Amplifying imperfect randomness through quantum mechanics.
A fundamental question is: do completely unpredictable events exist? While quantum theory makes probabilistic predictions, this does not imply that nature is random, as randomness should be certified without relying on the complete structure of the theory being used.
For example, the well-known Bell experiments of quantum mechanics produce perfect random bits but they require prior perfect randomness, falling into a circular reasoning. ICFO group fix this problem by providing a Bell test that uses arbitrarily imperfect random bits to produce bits that are, under the non-signalling principle assumption, perfectly random. This gives the first protocol attaining full randomness amplification. Our results have strong implications to the debate of whether there exist events that are fully random.
7. Quantum algorithms and low-degree polynomials.
We have studied two notions:
• The smallest number of queries for a quantum algorithm computing a function f(x1, …, xN).
• The smallest degree of a polynomial approximating f(x1, …, xN).
In collaboration between LU and CWI, we show that, if f(x1, …, xN) depends on all variables, both of those quantities have to be of the order (log n/loglog n), and we exhibit functions for which this bound is achieved. This is interesting for both quantum algorithms and for classical complexity theory (because approximate degree is also important in the classical context).