Academic CentreNews
Andris Ambainis from University of Latvia presented a paper "Superlinear advantage for exact quantum algorithms" in which he finds the first exact quantum algorithm (a quantum algorithm that always outputs the correct answer) that is better than classical by more than a factor of 2. This solves a well known open problem that has been open for more than 10 years.
Amnon Ta-shma from Tel-Aviv University presented a paper "Inverting well conditioned matrices in quantum logspace" in which he constructs small space quantum algorithms for several important linear algebra problems.
This is the first example where quantum algorithms show an advantage in terms of space (rather than time, for which we know many faster-than-classical quantum algorithms).
STOC is one of two leading theoretical computer science conferences in the world and is the place for presenting the most important results in the field.
June 2013: QCS research at CCC 2013 QCS research was strongly featured at the 28th IEEE Conference on Computational Complexity (CCC 2013) at Stanford University, USA.
Ronald de Wolf (CWI) gave an invited talk "Quantum proofs for classical theorems" on one of topics of the QCS project: using ideas from quantum information to prove results in classical computer science.
Two regular papers with results of QCS project were also presented:
- A. Ambainis (Univ. of Latvia) and R. de Wolf (CWI), How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
- A. Belovs (Univ. of Latvia) and A. Rosmanis (Univ. of Waterloo), On the Power of Non-Adaptive Learning Graphs.
The paper by Belovs and Rosmanis was awarded Ron W. Book Best student paper award.
March 2013: Andris Ambainis to receive Grand Medal of Latvian Academy of Sciences
QCS coordinator has been awarded the Grand Medal of Latvian Academy of Sciences. The Grand Medal is the top award for research in Latvia and is given to two researchers each year. Andris Ambainis is by far the youngest scientist to receive this award, at an age of 38.
November 2012: Andris Ambainis wins ERC Advanced Grant QCS researcher Andris Ambainis has won an Advanced grant for the project "Methods for Quantum Computing" from European Research Council (ERC) - the most prestigious research funding organization in Europe. This is the first ERC Advanced Grant in any of the Baltic countries (Estonia, Latvia, Lithuania). Andris Ambainis is also among the youngest researchers who have won an ERC Advanced Grant, at the age of 37. October 2012: QCS researcher Jop Briet wins award for best Ph.D. thesis in mathematics On October 30, QCS researcher Jop Briët from Centrum Wiskunde & Informatica (CWI) in Amsterdam, was awarded the Stieltjesprijs 2011, the prize for the best thesis in mathematics in Netherlands. In 2011 Briët defended his thesis `Grothendieck Inequalities, nonlocal games and optimization’ at The University of Amsterdam under the supervision of Prof. H. M. Buhrman. In his thesis Briët introduced new variants of the famous inequality of Grothendieck and applied them to computer science, physics and mathematics. Briët’s thesis was selected out of sixty entries. The award is made available by the Dutch foundation ‘Stichting Compositio Mathematica’. For more information, see: http://www.cwi.nl/news/2012/stieltjes-award-jop-bri%C3%ABt-centrum-wiskunde-informatica October 2012: Nature does not allow secure computation between rivals It is impossible to devise a cryptographic system that guarantees secure computation between two rivals. Researchers of Centrum Wiskunde & Informatica (CWI), University of Amsterdam (UvA) and ETH Zürich prove this in an article in Physical Review Letters that appeared on October 17. This was already known for classical communication, but the researchers prove that even with the use of quantum communication, devising a fundamentally secure cryptographic protocol is not possible. Secure computation between two mutually distrusting parties is a fundamental problem in modern-day cryptography. A famous example is the millionaire problem. Two millionaires want to find out which one of them is the richest, without disclosing their wealth to each other. Is there a secure protocol that they can follow to calculate who is the richest? According to Harry Buhrman (CWI), Christian Schaffner (UvA) and Matthias Christandl (ETH Zürich), this is impossible:one of the parties can always discover the wealth of the other by cheating. The reason lies in the fundamental laws of nature described by quantum mechanics. More information: prl.aps.org/abstract/PRL/v109/i16/e160501 www.cwi.nl/news/2012/nature-does-not-allow-secure-computation-between-rivals October 2012: QCS research presented at FOCS 2012 Two QCS groups presented their research at the 53rd IEEE Conference on Foundations of Computer Science (FOCS 2012) in New Brunswick, USA. Aleksandrs Belovs from University of Latvia presented a paper "Learning-graph-based Quantum Algorithm for k-distinctness" which extends his "learning graph" framework for designing quantum algorithms and uses it to solve k-distinctnes, a long-standing open problem in quantum algorithms. Researchers from University of Paris - Diderot presented the paper "Lower bounds on Information Complexity via zero-communication protocols and applications" by Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland and David Xiao which applies methods from quantum information to communication complexity of purely classical problems.
FOCS is one of two leading theoretical computer science conferences in the world and is the place for presenting the most important results in the field. July 2012: Iordanis Kerenidis wins ERC Starting Grant QCS researcher Iordanis Kerenidis has won a Starting grant on "Quantum Communication and Cryptography" from European Research Council (ERC) - the most prestigious research funding organization in Europe. June 2012 - QCS researchers present the first demonstration for experimentally assessing the dimension (dimension witness) of an unknown quantum system from measurement data alone The paper "Experimental estimation of the dimension of classical and quantum systems" has been published in Nature Physics by ICFO Research fellow Dr. Martin Hendrych, ICFO PhD Student Rodrigo Gallego, Prof. Nicholas Brunner (U. Bristol, UK), Dr. Michal Micuda, (ICFO, U. Palacky, Czech Republic), ICREA Prof. Antonio Acin, leader at ICFO of the Quantum Information group and UPC Prof. Juan P. Torres, leader at ICFO of the Quantum Engineering of Light group. Link to the paper: www.nature.com/nphys/journal/vaop/ncurrent/full/nphys2334.html May 2012: QCS researchers win Best Paper award at STOC'2012 QCS researchers have won the Best Paper award at STOC'2012 (one of two leading theoretical computer science conferences in the world) for a paper that brings together quantum information and classical computer science: S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. 44th Annual ACM Symposium on Theory of Computing (STOC 12), pp.95-106 In this paper, we solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. January 2012: Sandu Popescu wins ERC Advanced Grant University of Bristol professor Sandu Popescu was awarded an European Research Council (ERC) Advanced Grant for €1.66 million for his project ‘Nonlocality in Space and Time (NLST)’. December 2011: QCS research presented at QIP 2012 Members of the QCS project participated in the 15th International Workshop on Quantum Information Processing (QIP'2012) in Montreal, Canada, December 12 - 16, 2011, presenting a number of talks and posters. One of main highlights of the conference was the plenary talk "Span Programs for Functions with Constant-Sized 1-certificates" by Aleksandrs Belovs from University of Latvia. His paper was one of only 4 QIP submissions (out of more than 150) which were selected for plenary talks. QIP researchers were also involved in 2 (out of 9) featured talks:
- André Chailloux and Iordanis Kerenidis, "Optimal Bounds for Quantum Bit Commitment"
- Gilles Brassard, Peter Høyer, Kassem Kalach, Marc Kaplan, Sophie Laplante and Louis Salvail, "Merkle Puzzles in a Quantum World". Among 28 contributed talks, 6 involved QCS researchers. The large number of QCS contributions at QIP showed the leading role of the QCS project in the theory of quantum information. February 2011: QCS project presented at the University of Latvia annual conference On February 3, 2011, prof. Ambainis, coordinator of the QCS project, presented the project at the plenary session of the 69th Annual scientific conference of the University of Latvia. The plenary session "EU Financed Research in Latvia. Opportunities for Basic Research in FP7" was organized by University of Latvia, jointly with FP7 National Contact Point. The goal of the plenary session was to showcase the opportunities for basic research in FP7. The program included presentations by representatives from European Research Council and Austrian and French FP7 contact points. We were invited to present the QCS project as a success story in which a Latvian basic research project has succeeded in a highly competitive FP7 subprogramme. January 2011: Results of QCS project presented at QIP 2011 Members of the QCS project participated in the 14th International Workshop on Quantum Information Processing (QIP'2011) in Singapore, January 10 - 14, 2011, presenting a number of talks and posters. QIP is the leading international conference on the theory of quantum information. This year’s QIP attracted more than 300 participants. From 8 plenary talks, 2 involved the members of the QCS project:
- "An efficient test for product states, with applications to quantum Merlin-Arthur games" by A.Montanaro (University of Cambridge) and A.Harrow (University of Washington);
- "Position-based quantum cryptography: impossibility and constructions" by S.Fehr (CWI), H.Buhrman (CWI), N.Chandran (UCLA), R.Gelles (UCLA), V.Goyal (Microsoft Research), R.Ostrovsky (UCLA), C.Schaffner (CWI).
- "Parallel repetition of entangled games" by J.Kempe (University of Paris) and T.Vidick (University of California, Berkeley);
- "Near-optimal and explicit Bell inequality violations" by H.Buhrman (CWI), O.Regev (ENS Paris), G.Scarpa (CWI) and R. de Wolf (CWI);
- "Finding is as easy as detecting for quantum walks" by H.Krovi (University of Connecticut), F.Magniez (University of Paris), M.Ozols (University of Waterloo) and J.Roland (NEC Laboratories America).
Agnis Škuškovniks, the representative of the QCS Project, explains the objectives of the project.