In the quest for obtaining a working quantum computer, it is interesting and important to find out how classical and quantum computers olve computational tasks and if quantum computers can do better. On 16 February PhD student Subhasree Patro (CWI and QuSoft) defended her PhD thesis entitled 'Quantum fine-grained complexity' at UvA, which explores this topic.
Computer scientists try to solve computational problems efficiently, like, for example, computing the 'edit disctance' (similarity) between two strings, or computing the shortest path from one city to another (like in a navigation system). QuSoft and CWI 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 - qubits - can exist in a so-called superposition of those values. This means that 0 and 1 can coexist and be computed on at the same time. Along with the fact that there can be interference, this offers some advantages. As quantum computers have intrinsically different inner workings, they can solve the same problem in other ways than a classical computer.
The broad question is then: ‘Can this and other properties of quantum systems be useful for solving computational problems in a more efficient and faster way than the existing classical algorithms can do?’
In her PhD research, Subhasree Patro 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 is not always the case: it does not happen for all kinds of problems. Sometimes, for example, the quantum algorithms are not faster than the classical ones (there are examples of computational problems where this is witnessed). Patro: "However, these known techniques don’t work for computational problems with ‘super-linear quantum complexity’". In her thesis Patro presents frameworks with which, under reasonable assumptions, one can prove ‘super-linear quantum time lower bounds’.
Similar work is being done in the classical setting using so-called ‘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.
In her thesis, Patro translates some of these results of classical fine-grained complexity theory to the quantum domain. The translations are not trivial. Along with her co-authors Patro develops frameworks and techniques with which one can study the complexity of computational problems in the quantum setting. They show that, under reasonable assumptions, 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: these results are important for the industry as it means they should not 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.
Subhashree Patro can be reached through Patro's personal website. A more in-depth description of Subhasree's work can be found in a video presentation of Patro's work at CWI.
Source: QuSoft's news item on Subhasree Patro's PhD defence.
Edits & header image: CWI.
