Academic participants:
Andris Ambainis, Gilles Brassard, Richard Cleve, Peter Høyer, Michele Mosca, Ashwin Nayak, Alain Tapp.
Partners:
Perimeter Institute and Canadian Institute for Advanced Research.
We will study topics in quantum complexity theory related to quantum algorithms. This includes quantum lower bounds and reductions. Historically, studies of these topics have provided important and useful insights into quantum algorithms. For example, the lower bound for quantum search showed that Grover’s algorithm is optimal and solving NP-complete problems by a quantum computer requires an approach different from a black-box search. Also, Aaronson and Shi showed a lower bound for the collision problem, which is related to the concept of a “collision-resistant hash function”, which is an important primitive for cryptography. The result indicates that it may be possible to construct collision resistant hash functions that would be secure against an adversary possessing a quantum computer.
Examples of areas that we will study are the complexity of graph and matrix problems. This area has a variety of open problems that can be studied in the black-box (query) model, for example, finding a perfect matching in a graph, finding a triangle in a graph and matrix multiplication. We will work on quantum lower bounds for these problems.
We will also consider lower bounds on the amount of memory required by fast quantum algorithms in the query model. For several problems, such as element distinctness, the best known quantum algorithms use a large amount of quantum memory. We will work on a timespace lower bound showing that any quantum algorithm using a certain amount of queries requires a certain amount of quantum memory.
This project will complement our projects to find better algorithms for these problems. Historically, studying complexity theory problems has provided important and useful insights into the design of algorithms.
This project will interact with project QC2 on the implications of quantum algorithms for classical cryptography. Researchers part of this Network located at Perimeter Institute and also the one funded by the Canadian Institute for Advanced Research will investigate the fundamental issues relevant to this project.