In the quest for obtaining a working quantum computer, it is interesting and important to find out how classical and quantum computer perform similar tasks and if quantum computers are better.
On February 16th, 2023 (13:00 – 14:30, Agnietenkapel, Amsterdam) Subhasree Patro will defend her PhD thesis entitled “Quantum fine-grained complexity” which explores this topic.
Computer scientists try to solve computational problems efficiently, computing the edit distance between two strings, finding whether a graph contains a triangle of a certain weight or computing the shortest path from one city to another (like in a navigation system) are some examples of computational problems. QuSoft scientists are translating this work to the realm of quantum computers, which in principle have additional power due to the fact that they are able to resemble nature’s traits beyond classical computers. For a classical computer, bits can assume two possible values: 0 or 1. The quantum version of bits in quantum computers: the qubits can exist in a superposition of those values. This means that 0 and 1 can coexist and be computed on at the same time, this along with the fact that there can be interference offers some advantages.
As quantum computers have intrinsically different inner workings, therefore they can solve the same problem in different ways than a classical computer. The broad question then is ‘Can this and other properties of quantum systems be useful for solving computational problems in a more efficient/faster way than the existing classical algorithms solving those problems?’ Subhasree looked at a subset of problems that both a quantum and classical computer can solve, asking the question of whether a quantum computer can be faster. This does not happen for all kinds of problems. Sometimes indeed the quantum algorithms are not faster than the classical ones; there are examples of such computational problems already known where this is witnessed. However, these known techniques don’t work for computational problems with super-linear quantum complexity.
Subhasree in her thesis presents frameworks using which, under reasonable assumptions, one can prove super-linear quantum time lower bounds. These assumptions are necessary as proving such results unconditionally is hard both in the classical and quantum settings. Similar work is being done in the classical setting using fine-grained reductions where the method boils down to comparing the “difficulty” (complexity) of a problem by reducing this problem from one of which the complexity is widely conjectured. Subhasree in her thesis translates some of these results of classical fine-grained complexity theory to the quantum domain. The translations are not trivial. She along with her co-authors develops frameworks and techniques using which one can study the complexity of computational problems in the quantum setting. They show, under reasonable assumptions, that for a large array of very different computational problems quantum computers are essentially not faster than classical ones. Apart from theoretical progress, these results are of practical significance as well, they are important for the industry as it means it is not advisable to implement these problems on a quantum computer.
More information
Subhasree Patro performed her PhD research in the Algorithms and Complexity Group at CWI and within QuSoft. Her research was supervised by Harry Buhrman and Florian Speelman. This research was supported by the Robert Bosch Stiftung and additionally supported by NWO Gravitation grants NETWORKS and QSC, and EU grant QuantAlgo, and QuSoft.
She can be reached through her website. A more in depth description of Subhasree work can be found at this link.
