When: Thursday 19th May at 14.00
Where: Microsoft Teams - Online
Speaker: Nick Chancellor (Durham)
Hosted by: Andrew James
I will first give a brief review of solving hard optimisation problems through quantum computing in particular in a continuous-time as opposed to gate-model setting and then summarize some of our recent results in that area. I will introduce a key concept, adiabatic quantum computing, which solves problems a by relying on the adiabatic theorem of quantum mechanics to stay in a ground state. While the adiabatic theorem provides a useful theoretical handle to understand quantum computing in continuous time, solving hard problems adiabatically would require an exponentially long runtime and therefore unless P=NP (in non-computer-science terms unless there are no hard optimisation problems) will require either an exponentially long coherence time or a mechanism to restore coherence. On the other hand, algorithms which only succeed with an exponentially small probability may still be useful on more realistic devices, for which coherence time either does not scale, or scales only mildly. We find that even the simplest of these algorithms, a quantum walk which consists of evolution with a fixed Hamiltonian can provide better scaling on artificial spin glass problems than unstructured Grover-like search (a standard approach in quantum computing), this implies that the algorithm is using the structure of the problem. When parameters are swept over time rather than held constant, the scaling becomes dramatically better, and competitive with state-of-the-art quantum algorithms. I will discuss the theoretical reasons why these algorithms perform so well, which relate to the relative energy expectation of different terms of the Hamiltonian and give several examples to demonstrate how the theoretical tools we have developed work, following the results reported in [Callison et. al. PRX Quantum 2, 010338]. I will also touch on the potential relevance of this work to gate-model quantum computing through and algorithm known as the quantum approximate optimisation algorithm.
I will be sure to go through the background in a thorough way, in particular the aspects which relate more to computer science than physics.
Thursday, June 23, 2022 - 14:00 to 15:00
Thursday, October 13, 2022 - 14:00 to 15:00