I simply must open with this startling and memorable LinkedIn post that appeared on my feed this morning (thanks Shilpi Dubey Pathak!):
What did I talk about? I had two sessions – Get Your Business Quantum Ready Today and An Academic Capitalist View of Life – where, among a variety of topics, I mentioned my Four Pillars of Transcendental Engagement and my mantra of Leisure, Luxury and Pursuit of Newness:
What really made my morning was her phrase a terrific mind, that I would take any day and twice on Sunday, over:
A Beautiful Mind is a 2001 American biographical drama film about the mathematician John Nash played by Russell Crowe. The film is directed by Ron Howard based on a screenplay by Akiva Goldsman, who adapted the 1998 biography by Sylvia Nasar. It received generally positive reviews and went on to gross over $313 million worldwide (on a budget of $58 million), and won four Academy Awards, for Best Picture, Best Director, Best Adapted Screenplay and Best Supporting Actress.
Now to the main content of the post.
In 2022 (actually, we posted the first version on arxiv in December 2021, and it opened at #1 on Scirate, see The Power of the Bookish), Vikesh Siddhu and I created a TutORial (see Indianapolis 50):
Five Starter Pieces: Quantum Information Science via Semi-definite Programs.
Coincidentally, the same month as my TutORial talk at INFORMS:
The Royal Swedish Academy of Sciences has decided to award the 2022 Nobel Prize in Physics to
Alain Aspect, John F. Clauser and Anton Zeilinger
“for experiments with entangled photons, establishing the violation of Bell inequalities and pioneering quantum information science”
Our motivations for writing the tutorial:
The primary audience comprises of Operations Research (and Computer Science) graduate students who have familiarity with SDPs, but have found it daunting to become even minimally conversant with pre-requisites of QIS.
Thomas Sprat, in 1667, as historian at the Royal Society of London, noted a connection between being an outsider to a trade and inventiveness:
A glance from an angle might well reveal a new aspect of nature.
We would like to create such a trading zone through this chapter – and invite Operations Researchers and Computer Scientists – to foster innovative contributions to Quantum Information Science (QIS).
I found this book (from where I lifted the above quote) enjoyable and informative:
Here is (recall Witness for an Entanglement) a new paper, joint with Javier Peña, who indeed was intrigued by the above TutORial, where Problem 4 was on Quantum Entanglement and Separability, and Vikesh Siddhu:
Here is the abstract:
Quantum entanglement lies at the heart of quantum information science, yet its reliable detection in high-dimensional or noisy systems remains a fundamental computational challenge. Semidefinite programming (SDP) hierarchies, such as the Doherty-Parrilo-Spedalieri (DPS) and Extension (EXT) hierarchies, offer complete methods for entanglement detection, but their practical use is limited by exponential growth in problem size.
In this paper, we introduce a new SDP hierarchy, PST, that is sandwiched between EXT and DPS—offering a tighter approximation to the set of separable states than EXT, while incurring lower computational overhead than DPS. We develop compact, polynomially scalable descriptions of EXT and PST using partition mappings and operators. These descriptions in turn yield formulations that satisfy desirable properties such as the Slater condition and are well-suited to both first-order methods (FOMs) and interior-point methods (IPMs). We design a suite of entanglement detection algorithms: three FOMs (Frank-Wolfe, projected gradient, and fast projected gradient) based on a least-squares formulation, and a custom primal-dual IPM based on a conic programming formulation. These methods are numerically stable and capable of producing entanglement witnesses or proximity measures, even in cases where states lie near the boundary of separability.
Numerical experiments on benchmark quantum states demonstrate that our algorithms improve the ability to solve deeper levels of the SDP hierarchy. In particular, the PST hierarchy combined with FOMs enables scalable and effective entanglement detection in relatively easy instances, while our IPM approach offers robustness and early witness recovery for the more difficult ones. Our results highlight the benefits of tailoring algorithmic formulations to hierarchy structure to advance entanglement detection at scale.
Here are the essential contents of the paper:
These hierarchies are one-sided, in that they are outer-approximations, and complete, that is, they eventually converge to the set of Separable states. Two pictures may help illustrate our results. In the first case, we detect the entanglement in the given state because we found a witness W.
In the second case, we are unable to detect entanglement, because of a limit on computational time (or memory), but we can, nevertheless, indicate that it is not too entangled by finding another proximal state that is close to the set of Separable states.
The theoretical computational complexity results we prove sharpen known bounds for EXT, and we also provide bounds for our new hierarchy, PST. All of the compact formulations rely on our partition operators which allow us to reach much higher levels (k) of hierarchy (for both EXT and PST) than previously demonstrated.
Let me highlight some numerical results here.
First, our custom IPM can be significantly faster (4.48 v 1038.32 seconds) than the open source base, even for EXT hierarchy (using our compact formulation, without which the solver performance is abysmal):
Second, our PST hierarchy is stronger than EXT in that it detects entanglement when EXT could not:
Other results in the paper show that (3) When FOMs can detect entanglement, they are statistically faster than interior-point methods; (4) IPM with EXT hierarchy detected entanglement even when base could not (and no FOM did); (5) IPM with PST hierarchy detected entanglement when FOMs (with PST hierarchy) could not; (6) IPM is statistically faster (for both hierarchies) than base, and (7) IPM (and base) with PST hierarchy detected entanglement in all benchmark problems.
Looking forward to showcasing this work (and other papers, including Photonic Ising Machines and Quantum Queuing papers, both in collaboration with folks at IIT-Madras, and one on Quantum-inspired algorithm for FRNDP, in collaboration with Koc) at my Keynote (Sunday, October 26th , 545-645pm, Bldg A Lvl 4 A41) at 2025 INFORMS Conference in Atlanta:
How can INFORMS contribute to The Second Quantum Revolution?
Those interested in gently exploring Quantum Computing hands-on may want to attend (also on Sunday, October 26th, 245-4pm, Bldg A Lvl 4 A410) TutORial co-created with Arul Mazumder (Undergraduate, Rising Junior in CS, see Fun, Fun, Fun):
Five Starter Problems: Solving Quadratic Unconstrained Binary Optimization (QUBO) models on Quantum Computers.
Those interested in learning even more, please join me on Monday (October 27, 245-4pm, Bldg A Lvl 3 A302) for the
Panel on Quantum Computing and OR
moderated by Tamás Terlaky, along with Carleton Coffrin, Stefan Woerner, Ojas Parekh, and David Bernal.
It is 2025 – The International Year of Quantum – and we are celebrating 100th anniversary of Quantum Mechanics. See y’all there!
