Solving Diophantine Equations with Grover's Algorithm

Today on the arXiv a paper appeared, written by Lara Tatli and me.  The paper is on solving Diophantine equations on a quantum computer using Grover's algorithm.  

The project started last summer when Lara (an undergraduate physics student at Durham) got in touch to ask if she could do a summer project with me.  I had an idea to use a quantum search algorithm to find roots of equations in a more efficient way than a classical algorithm might, and I suggested to her we could start looking at that.  My initial idea was very vague but I thought perhaps we could encode floating point numbers in an interesting way search for values of x which solve f(x)=0 for some hopefully interesting functions.  This "root finding" is a common basic tool of numerical analysis and many problems can be formualted this way.

When looking at how to encode the numbers on a quantum computer, it became clear that starting from the simplest case - where the numbers are just straight binary representations of integers - would be the easiest place to start, but still interesting enough.  Equations where the numbers can only take on integer values are called Diophantine equations after Diophantus of Alexandria who studied them in the 3rd century.  The standard definition of Diophantine equations has them acting in at least two variables, and a simple example is finding all the Pythagorean Triples - the set of right-angled triangles with integer sides.  The basic example there is {3,4,5} since these integers satisfy Pythagoras' theorem 3²+4²=5².  There are an infinite number of solutions of the equation x²+y²=z² where x,y,z are all positive integers.  Fermat's Last theorem famously states that there are no solutions of xⁿ+yⁿ=zⁿ where x, y, and z are positive integers and n is an integer greater than 2.  

Anyway - our ambition is, at this stage, at the level of a simpler Diophantine equation, and we just looked at x+y=5, arbitrarily chosen.  Here, there are lots of solutions if you allow x and y to be negative integers, while if you restrict to x,y>=0 then there are solutions (x,y)=(0,5), (1,4), (2,3), (3,2), (4,1), (5,0).  This is what we were hoping to find.  

Grover's algorithm works by constructing a quantum phase oracle that can take a linear superposition of encodings of all possible (x,y) pairs within some range of values of x and y (we encoded each with 3 bits, so from 0 to 7) and change the phase of the quantum amplitude for each component of the linear superposition that represents a valid solution.  Then a neat trick uses quantum interference to amplify those states which had been marked out, while reducing the amplitude of the others.  In general several cycles of this marking and amplification can be needed to pick out the answers, but - crucially - fewer cycles than a non-quantum search.  It's a very standard quantum algorithm, first worked out by Grover in the 90s.  Applying it to simple Diophantine equations like we have done doesn't seem to be something that people have done before, though I dare say now our paper is up on arXiv, someone will come along and point out that it has been implemented already.  It's a pretty simple thing, but has the potential to be worked up in to a more powerful solver of more interesting equations.

Here's the final plot from the paper where we show the quantum state of the quantum comptuer after two iterations of Grover's algorithm, where we see that there are four quantum states picked out which we have labelled with the encoding of the x and y values.  If you split the 6-bit binary strings into two 3-bit strings for the values of x and y, you'll see they add up to 5.

What Englishman?

In older scientific journals,  you get the situation where one paper would end half way down a page and the next article would start on the same page.  So when, in this modern age, we download a pdf of a paper, we sometimes get the start of another paper, and sometimes they can be interesting things, if only because they are very much of their time and not something that we would deliberately download to read for its enduring relevance. 

I was prompted, by a talk at the CNR*24 conference that I went to last week, to look at a paper by Eugene Wigner entitled "Nuclear Reactions and Level Widths", Am. J. Phys. 17, 99 (1949).  The journal it's in - the American Journal of Physics - is a long-running educational journal with articles aimed at those interested in teaching physics, generally at the undergraduate level.  I am yet to read through the paper, but I did see on the last page an extra thing which is a poem reproduced from the British satirital magazine Punch.  I reproduce an excerpt as (I hope) fair usage, since I think the poem is still in copyright.  It's about some characters in electromagnetism and begins:

and then in verse 4 we have

where the "Englishman" referred to is James Watt (scientist, not the BrewDog guy).  I'm sure Scots everywhere will snort Irn Bru out their noses at this claim of Watt's nationality. 

I do remember Punch from the final years of its existence.  It carried on until 1992 (and was revived briefly later).  I don't think I ever read it much outside doctors' waiting rooms but I did struggle to see what ever was funny about it.  Perhaps I was too young to appreciate it, but perhaps also it was a rather old and conservative kind of humour.  Anyway, the poem, lighthearted in style as it is written, has an unwelcome nationalism to it, as well as that affectation that still continues to this day – that it's just fine to be a kind of intellectual and at the same time to admit in a happy way that you don't understand science.

Oh Vienna

 I'm making my first trip to the International Atomic Energy Agency (IAEA), my first trip to Vienna, and my first trip to Austria.  I'm attending the CNR'24 (Compound Nuclear Reaction) conference on the IAEA premises which is part of the UN buildings in Vienna.  It's a pretty amazing and iconic venue, though having to go through airport-type security to get in is a slight pain.  

The compound nucleus is the name given to the state of a reacting nucleus that occurs typically after the capture of a neutron or a heavier ion to form a highly excited state which is relatively long-lived and which quickly redistributes the nucleons from the impinging system in such a way that details of the initial reaction are 'forgotten' by the system.  The picture is sometimes given of marbles sitting in shallow bowl, or depression, with another marble coming in from outside with enough energy to pass through the depression, except that it knocks into the marbles already in there, shares its kinetic energy with them so that it gets captured and no individual marble has enough energy to leave.  In principle there is enough energy there so that after enough collisions one of the marbles can be kicked out, and eventually, in a frictionless ideal situation, such an even will happen.  In real compound nuclei sometimes this does really happen, and very narrow neutron resonances can be found which correspond to very long-lived states.  

The term "compound nucleus" was coined by Niels Bohr in the early days of nuclear physics when trying to understand some of the first-observed phenomena in nuclei and its impressive that the ideas were sufficiently correct that they have survived today.  Some of the calculations I am interested in, such as those creating giant resonances, causing fission, or during fusion to make superheavy elements, have this compound nuclear state as an intermediate nucleus.  I've never really thought about the properties of this compound nucleus in detail, but having talked to one of the conference co-organisers earlier in the year, I realised that I would find the conference pretty interesting, and so it has been.

I've been to many conferences over the years, and one of the things I've seen is the people who enjoy meeting up with colleagues who they have seen throughout their careers at different occasions and throguh such meetings form friendships which endure over the years.  I've somewhat felt that that's part of the conference experience that I've missed out on, partly through a natural diffidence that has perhaps affected my ability to form friendships outside of my professional life as much as in it, but here I have indeed bumped into a few people who I have really been able to catch up with and talk about the last time we have seen each other, mixing up asking about latest work results alongside how they are doing and how life has changed since seeing each other last.  It's a nice part of the conference experience.

Here's my obligatory blogpost picture - me standing in the plaza area of the UN complex

 

Proceedings from COMEX

 Last year, I attended COMEX7 in Catania, Italy.  This week, I spied a big brown envelope for me in the post room at work, and saw that it was from Italy, and couldn't quite figure out what might be inside.  At first I wondered if it was a hard copy of the new NuPECC Long Range Plan document.  But, no, it was a hard copy of the COMEX7 proceedings, published in a special issue of Nuovo Cimento C. 

Nuovo Cimento is a famous journal from Italy, set up by the Italian Physical Society, in which many interesting articles have appeared over the years - particularly on theoretical physics, and particularly from some of the famous Italian names, such as Fermi and Majorana.  As happens with many journals the original Nuovo Cimento split into different series with different specialities, and eventually almost all of them merged with other European national journals to form the European Physical Journal series.  But a few rump Nuovo Cimento journals live on.  Nuovo Cimento C survives to publish proceedings of conference and workshops held (mainly? solely?) in Italy.  And so, I have a hard copy of a special edition of this famous and historic journal, which includes my first, and perhaps only, Nuovo Cimento paper

The front cover

My paper!

 

2023 Journal Impact Factors

I see that the 2023 Journal Impact Factors (JIFs) have been announced.  While I take them with a pinch of salt, as I am able to judge quality of articles by actually reading them, JIFs are an interesting artifact of the research environment, not least because so many people seem to take them seriously.

In the "PHYSICS, NUCLEAR" category, there are 20 journals, with the top two predictably being review-only journals.  For the regular journals, where you can openly submit papers, there are not too many surprises:  The journals which combine particle and nuclear phsyics, but which are nevertheless included in the "PHYSICS, NUCLEAR" category, do better than nuclear-physics-only journals.  So Physics Letters B, Chinese Physics C and J Phys G outrank Phys Rev C, European Physical Journal A and Nuclear Physics A.    

The one unexpected result for me is the high score of Nuclear Science and Techniques.  The journal combines nuclear physics of the sort I do, with "nuclear science" - meaning things to do with applications of nuclear physics, such as nuclear reactors, or radiation physics.  Such areas do not usually bring JIFs up as applied physics tends not to be highly cited.  The journal has been somewhat under my radar.  I don't make a habit of looking there for new papers, though I see there are some interesting nuclear physics papers there, alongside nuclear science articles a bit far from my main interests.  It's a China-based journal, though published by Springer, and the authorship is heavily China-based.  

One may speculate why it is doing so well in impact factor. The JIF number has jumped out quite a bit this year to put it in the top quartile by category.  I don't know the answer as to why.  It may simply be the fact that the journal is heavily used in China and the volume of reesarch coming out from China, whose authors are aware of and citing other work from China, is ever-increasing.  Let me know what you think!

Since I like to include a picture for each post, I scanned a list of open access papers in the journal and found the one closest to my own interests - The 5𝛼 Condensate State in Ne-20 by non-Chinese author Takahiro Kawabata.  It shows a schematic picture of an alpha-cluster state in neon-20 compared to the non-clustered ground state.

Hackathon wrap-up

As mentioned in a previous post, we (me, postdoc Abhishek, and student Grant) were in Edinburgh attending a hackathon run by DiRAC, the computing arm of the UK STFC funding agency, and Codeplay, an Edinburgh-based company with expertise particularly in the Intel architecture of hardware and software.

At the start, we had our code (Sky3d) which runs on CPU and makes extensive use of a CPU-based fast Fourier transform library (fftw).  By the end, we had, with extensive help from the DiRAC and Codeplay engineers, a code which was mainly hosted on the CPU but which offloaded parts of its operation to a GPU coprocessor.  In particular, we were able to interface to a custom set of fft routines which are part of the Intel MKL library and which we were able to use fftw wrappers for.  This was all pretty exciting - we are using the latest hardware, with very new compiler technology, to run our code.  The hope is that it should end up running so much faster that we will be able to attack physics questions that are just too hard / time consuming to answer right now. The down side is that so far, the GPUified code actually runs slower than the CPU-only code.  This is presumably because it is spending time shunting too much data between the CPU memory and the GPU memory and not enough time powering through calculations on the GPU.  So we still have a lot of work to do to get a fully optimised GPU version of Sky3d, but at least we have started now.

At the end of the three day event, Grant and I went to a chip shop.  Grant tried the local delicacy of a deep-fried battered Mars bar.  He liked it.  I didn't fancy one but have tried one before and think they're pretty good! 

Grant with a deep-fried battered Mars bar

Developing quantum computing algorithms for the nuclear shell model

Today our new paper appeared (as an "in press" draft) in the New Journal of Physics.  In it, we develop quantum computing circuits that can produce eigenstates in the nuclear shell mode.  This nuclear model, called "configuration interaction" in other areas of many-body quantum mechanics, such as quantum chemsitry, is probably the main approach that realistic calculations of nuclei have been attempted on quantum computers by various groups.

Our paper is by no means the first to explore how to apply quantum computing to the shell model.  What we have done, though, is to use a circuit ansatz inspired by the nuclear physics and the symmetries involved to use a small number of gates, and a small number of variational parameters in order to turn the initial "zero" state of the quantum computer register into a state which simulates the nuclear wave function. 

The result is that we are able to find, with relatively low-depth circuits, the ground state, lowest 2+ and 4+ states, on a simulated quantum computer with good accuracy.  

We had some useful comments from the referees pointing us to how we might be able to reduce the circuit depth further, and we will look into that.  We also would like to really test the circuits on a real quantum computer.

Here's an example circuit - probably our most complicated one - that finds the 2+ state of Nickel-58