Nuclear reactors run on a delicate balance: too few neutrons and the chain reaction dies out, too many and it runs away. Calculating that balance – the neutron diffusion k-eigenvalue problem – is fundamental to reactor safety, fuel management and radiation transport modelling, but realistic models with complex geometries and heterogeneous materials can produce billions or even trillions of unknowns. Andrew Childs and his colleagues have proposed a hybrid classical-quantum algorithm that takes this problem on, drawing on quantum linear-system algorithms, quantum preconditioning and Hamiltonian simulation.
Childs is a Professor of Computer Science at the University of Maryland, Interim Director of the University of Maryland Institute for Advanced Computer Studies (UMIACS), Director of the NSF Quantum Leap Challenge Institute for Robust Quantum Simulation (RQS), and a Fellow at the Joint Center for Quantum Information and Computer Science (QuICS). His research centres on quantum algorithms – particularly quantum simulation and methods for reducing the computational resources needed to simulate physical systems.
SCW spoke to Childs about the state of quantum algorithms research, why comparing classical and quantum performance is harder than it looks, and what the neutron transport work reveals about where real quantum speedups might – and might not – be found.
Tell us about the key developments in quantum algorithms research over the past year
Andrew Childs: My area is really quantum algorithms, which includes trying to better understand applications of algorithms that have already been developed, for example, how to use quantum simulation algorithms to simulate particular kinds of physical systems.
Another class of things I'm interested in is using quantum algorithms for scientific computing, giving algorithms for differential equations on quantum computers, and understanding how much speedup they can offer. I'm also pretty interested in fundamental questions about the power of quantum computers and in relating their performance to that of classical computers in abstract models, where you have a clean formulation of a problem and try to make a precise mathematical statement about how they relate.
The closer you get to applications, the harder it is to make precise statements, because the performance of algorithms can be difficult to understand. When you want to compare the performance of classical and quantum algorithms, many of the classical algorithms people use are pretty sophisticated, and people don't necessarily worry so much about proving theorems about how they perform; they just have algorithms, implement them, and they work in some computing system.
But in the quantum computing world, we still don't have really good devices – the actual computers are very limited in what they can do. The progress is amazing; there's a lot happening, but there are still no large-scale, utility-scale devices where you can really run useful simulations. So, in practice, comparing classical and quantum algorithms is largely limited to understanding classical performance and then comparing it to what we can prove about quantum performance, which makes it pretty hard to draw meaningful comparisons.
How do you measure quantum algorithm performance against classical algorithms?
AC: There are cases where you can give some analysis of the performance of a quantum algorithm; you can say the running time will scale in a certain way with some parameters of the problem. Those kinds of statements are generally possible to make, depending on the details, for some kinds of algorithms, and that gives you some indication of how the algorithm performs.
That doesn't necessarily mean it couldn't actually perform better; you do some analysis, make some approximations, and something might be loose somewhere, so the actual performance could be better. But it establishes a baseline for the algorithm's performance. The trickier side is comparing that to the performance of classical algorithms, because generally, putting an upper bound on the running time of an algorithm is doable, but lower-bounding how long an algorithm will take is harder, especially if you want to think about the time it takes on practical, real-world instances, which is hard to characterise with a theoretical framework.
How does quantum computing apply to nuclear reactor simulation?
AC: A concrete example of this is a paper we recently wrote on understanding neutron transport. These kinds of problems can model the behaviour of nuclear reactors: you have neutrons moving around in the reactor, and a differential equation describing that neutron transport problem, and you try to understand properties of it with an algorithm. This is obviously a practical thing people actually want to do, because they want to understand how these things perform.
We developed a quantum algorithm for this, using ideas from quantum algorithms for differential equations, and we have some analysis of its performance. To get it to perform well, we have to do things in the right way; there's essentially a linear-system-solving problem involved, and we care about the condition number of that linear system, so we have to do some preconditioning to make the condition number good, and show how to implement that preconditioned linear system efficiently on a quantum computer. There are things to work out, but once we do, we can bound how long it would take the quantum computer to run the algorithm and produce information about the solution. But the hard part of this problem is understanding how it compares to the best classical algorithms.
In the paper we wrote, the quantum algorithm essentially discretises the system of differential equations on a uniform grid, and we compare its performance against an analogous classical algorithm that discretises everything on a uniform grid in the same way.
There, it looks like there's a polynomial quantum speedup between the two approaches; the speedup is somewhat limited, but in that context, there does appear to be some quantum speedup. But then, of course, you can consider other classical algorithms. This isn't really my area, but as I understand it, people generally approach these differential equations using finite element analysis, and just discretising uniformly isn't necessarily the best approach. If there's some part of the system where something interesting is happening, you should discretise more finely there, and more coarsely where things are smoother and better behaved. If you do that, the speedup could disappear as the classical algorithm improves.
How can quantum algorithms keep their speedup over improving classical methods?
AC: One way is to just wait until we have big devices and implement these things. If they're useful, they're useful, and it doesn't really matter what you can prove about them; that's definitely an approach. But it's also possible to do what we can with the tools we have.
For example, for particular model problems you're studying, you can try implementing alternatives to the uniform discretisation, a reasonable choice of non-uniform discretisation, and see how it performs. Maybe empirically the speedup goes away, and that's an indication that's not a place to look for speedup, which is still a useful result, because it can tell you what you should do differently to find a problem where you'll get more advantage from quantum algorithms.
Exploring particular classical approaches is definitely something one can do, especially since people who dedicate their lives to developing methods for solving differential equations on classical computers have a lot of intuition about the right way to do it. So this is probably a place for collaboration between people thinking about quantum algorithms and people with expertise in classical methods for solving these problems.
Are there trade-offs from having so many different underlying technologies, topologies and architectures?
AC: It makes things more complicated, but that also means more choice, more things to explore. I don't feel like it's a huge burden though. If you want to focus on the big picture of what quantum computers can do, you just work in the basic quantum circuit model, where you can do gates between any pair of qubits; that's what the vast majority of my papers consider, and I think it gives a good idea of what's going on. It adds some complexity in some cases, but I don't think it's the main barrier to understanding the power of quantum computers; it's manageable.
What is the biggest barrier to practical quantum computing?
AC: I think the most important barrier is coming up with quantum algorithms for new problems and understanding their performance. And, of course, the challenge of actually implementing quantum computers, which will really change the landscape, because if you can just try things out and be much more empirical, it's a completely different ball game.
Andrew Childs is a Professor of Computer Science at the University of Maryland. Childs is the Interim Director of the University of Maryland Institute for Advanced Computer Studies (UMIACS), Director of the NSF Quantum Leap Challenge Institute for Robust Quantum Simulation (RQS) and a Fellow at the Joint Centre for Quantum Information and Computer Science (QuICS).
