TRTR: Tayur Reformulated Track Reconstruction

When I was in high school, at Hyderabad Public School (Begumpet), my friends used to call me TR.

Why?

Sridhar is a common enough Indian name, and so, many of us have to be called something else for unique identification, especially in South India. Until I decided to apply to US Universities for grad school, my name on school and college (yes, even at IIT-Madras) transcripts was TR Sridhar.

Since “Mr.T” was already taken (The A-Team!), I expanded T and became Sridhar R. Tayur. 😏

When I meet my high school friends, even now, almost 40 years after our graduation, they call me TR. 

Let us switch to particle physics.

As you know, to pass time during these COVID19 times, among other things, I decided to get into Quantum Field Theory (QFT). 

This is just a type of math.

Of course, the reason this math is taken seriously – although pretty much every one can see and agrees that it is super-contrived, the modern-day equivalent of Ptolemy’s epicycles – is that its predictions are experimentally verifiable and dazzlingly accurate.

How are they verified?

This takes us to experimental particle physics.

I have previously discussed Higgs in There is something about Mass.

One cannot directly see an elementary particle. Instead, one has to infer its existence by looking at the tell-tale tracks that it leaves in the environment.

Like tracking down a wild-animal by following its footprints.

After a controlled smashing in the Large Hadron Collider (LHC) – say between two protons that have been circling in opposite directions, being accelerated to very high speeds – what the experimental physicists get – through hundreds of different sensors – are readings that emerged from the explosion, the tracks of the elementary particles, the footprints, for instance, the curved paths of charged particles in a magnetic field.

There are many elementary particles moving at once. 

The observed readings are noisy.

This brings us to an important computational math problem in experimental physics:

Track Reconstruction.

This is a canonical problem, and has been studied extensively by physicists.

I just wanted to know how they were reconstructing these tracks, for “merely fun” as I was curious. Time pass, we called in high school.

As I started reading my very first paper on this topic that I found via Googling (co-authored by Caltech experimental physicists, see top of the post), I instantly came up with how I might do it differently!

In what way, different? 

Track reconstruction (TR) can be reformulated as a variation of Cardinality Boolean Quadratic Problem (CBQP)! 

Why did this formulation magically emerge in my mind?

Because Tepper Quantum Computing Group’s Graver Augmented Multi-seed Algorithm (GAMA) is a novel algorithm that can solve CBQP very quickly. We posted our paper almost exactly one year ago!

This is a quantum-inspired classical algorithm. 

Of course, we can solve it on D-Wave as well, but then we would not be taking advantage of the special structure of the constraints.

It is a wonderful application of our research in Quantum Integer Programming (QuIP), the field I created in 2018, to solve Business problems, say in supply chain management.

How could we solve this problem?

 Step 1: Reformulate TR as a variation of CBQP.

 Step 2: Use GAMA with the appropriate Graver basis.

Is it better? I don’t know. We will find out!

Hoping that Hilbert’s observation works for us here:

A perfect formulation of a problem is already half its solution.

I am just so excited that we may have stumbled upon a new way of solving a canonical problem that is of importance to experimental physicists!