Neo-Quantum Organon, Book One: Quantum Integer Programming (QuIP)

239 0

Cheeky? Insolent? Audacious?

Perhaps all three! I suspect that Francis Bacon would have appreciated the chutzpah, even if Aristotle would have found it too lighthearted, insouciant, and way too playful. 

In a holiday mood, I could not resist a quippy post about Quantum Integer Programming, QuIP, a phrase that I coined. 

When I first cursorily surveyed the quantum computing (QC) literature in the summer of 2017, with an Operations Research (OR) and Operations Management (OM) lens, I could hear Francis Bacon:

That the state of knowledge is not prosperous nor greatly advancing, and that a way must be opened for the human understanding entirely different from any hitherto known…

Novum Organum was first published in 1620. It turns out that CMU has, as part of Posner collection, an original version! I was at Posner Center recently for a meeting and I saw it as I entered the conference room. And early January 2020, I am speaking at Cambridge (on Quantum!) where Francis Bacon attended University (at the age of 12).

I founded (in 2018) the Quantum Computing Group (QCG) at Tepper to (borrowing from Aphorism CXVI – Book One):

“lay more firmly the foundations (of quantum computing) and extend more widely (their applications)” by developing novel tools for optimizing, compiling and analyzing speedup.

Our approach to quantum computing is distinctly different, using fresh mathematics to create a bouquet of new tools, because we think differently

Paraphrasing Bacon (Aphorism CXXIII, Book One) as to why we may think differently:

I may say then of myself that which one said in jest (since it marks the distinction so truly), “It cannot be that we think alike, when one drinks water and other drinks wine.” Now other men drink a crude liquor like water. Whereas I pledge mankind in a liquor strained from countless grapes, from grapes ripe and fully seasoned, collected in clusters, and gathered, and then squeezed in the press, and finally purified and clarified in a vat. And, therefore, it is no wonder if they and I do not think alike.

What has always impressed me most about Bacon was his good understanding of the production process of wine. 😏

Concretely, we are asking these twin questions:

What can Quantum Computing (QC) do for Integer Programming (IP)?

What can Integer Programming (IP) do for Quantum Computing (QC)?

We are motivated primarily by applications of integer programs, such as: 

Quantum and Quantum-inspired Methods for de novo Discovery of Altered Cancer Pathways

With our methods, we can find cancer pathways so much faster (for Acute Myeloid Leukemia, AML, for instance, from data obtained from The Cancer Genome Atlas, TCGA).

In particular, Bacon will likely appreciate (from Aphorism CXXIX – Book One) our Graver Augmented Multi-seed Algorithm (GAMA): much higher a thing to discover that by means of which all things else be discovered with ease!

Why not take advantage of decades of advances in Computational Integer Programming, the heart of operations research contributions, to develop practical algorithms for compiling on quantum computers?

Here we go, in the reverse direction, to see what IP can do for QC (in collaboration with NASA Quantum and AI Lab, QuAIL):

Integer programming techniques for minor-embedding in quantum annealers

You may also enjoy an earlier expository paper (which concludes with a breezy summary of 4000-year history of relevant mathematics) in Science and Culture, where we cover the twin questions:

What can Quantum Computing do for Algebraic Geometry?

What can Algebraic Geometry do for Quantum Computing?

You can access these and many other papers on compiling on quantum computers and understanding quantum speedup through our research website at Tepper.

Happy Holidays!

Leave a Reply