This post was contributed by Martin Schuetz, Ruben Andrist, Grant Salton, and Helmut Katzgraber from the Amazon Quantum Solutions Lab, and Pierre Minssen, Romina Yalovetzky, Shouvanik Chakrabarti, Dylan Herman, Niraj Kumar, Ruslan Shaydulin, Yue Sun, and Marco Pistoia from JPMorgan Chase
Many companies face combinatorial optimization problems and across both science and industry there are prominent examples in areas like transportation and logistics, telecommunications, manufacturing, and finance.Analog neutral-atom quantum machines can provide a novel platform to design and implement quantum optimization algorithms, with scientists in both industry and academia searching for the most promising types of problems for which an early quantum advantage could be demonstrated.
Over the past year, the Amazon Quantum Solutions Lab (QSL) has worked together with the Global Technology Applied Research team at JPMorgan Chase to conduct a systematic study of the hardness of certain optimization problems, inspired by real-world use cases in finance.
In this post, well describe our project and summarize the key results. Motivated by recent experiments reporting a potential super-linear quantum speedup [2], we studied the problem native to Rydberg atom arrays (the maximum independent set problem on unit-disk graphs). We identified a class of problem instances with controllable hardness and minimal overhead for neutral atom quantum hardware.
We think this work sets the stage for potentially impactful future experiments towards quantum advantage. For further technical details, feel free to check out our original work published in Physical Review Research [1].
Given its potentially far-reaching impact, the potential demonstration of quantum speedups for practically relevant, computationally hard problems has emerged as one of the greatest milestones in quantum information science. Over the last few years,Rydberg atom arrays have established themselves among the leading contenders for the demonstration of such quantum speedups; see this blog post for more details. In particular, in Ref. [2] a potential super-linear quantum speedup over classical simulated annealing has been reported for the maximum independent set problem (MIS) on unit-disk graphs (MIS-UD), based on variational quantum algorithms run on Rydberg atom arrays with up to 289 qubits arranged in two spatial dimensions.
This work focused on benchmarking quantum variational algorithms against a specific implementation of simulated annealing (representing a classical analogue of the adiabatic algorithm), yet it left open the question of benchmarking against other state-of-the-art classical solvers. In our work, we study the MIS-UD problem in detail (see Figure 1 for a schematic illustration), with a broader range of classical solvers beyond the scope of the original paper. Our main goal is to empirically assess the hardness of the MIS-UD problem, to help zero in on problem instances and system sizes where quantum algorithms could ultimately be useful, and thus identify the most promising directions for future experiments with Rydberg atoms.
Figure 1. Schematic illustration of the problem. (a) We consider unit-disk graphs with nodes arranged on a two-dimensional square lattice with side length L and ~80% of all lattice sites filled, and edges connecting all pairs of nodes within a unit distance (illustrated by the circle). (b) Our goal is to solve the MIS problem on this family of Union-Jack-like instances (as depicted here with nodes colored in red in the right panel) and assess the hardness thereof using both exact and heuristic algorithms.
The MIS problem is an important combinatorial optimization problem with practical applications in network design, vehicle routing, and finance, among others, and is closely related to the maximum clique, minimum vertex cover, and set packing problems [3]. Here we provide two complementary problem formulations, one based on an integer linear program and one based on an Ising-type Hamiltonian compatible with Rydberg atom arrays. We discuss important figures of merit to assess problem hardness.
Consider a graph G = (V, E) with vertex set V and edge set E, with an independent set defined as a subset of vertices that are not connected with each other. The MIS problem is then the task to find the largest independent set. Introducing a binary variable xi for every node (with xi = 1 if node i is in the independent set, and xi = 0 otherwise), the MIS problem can formally be expressed as a compact integer linear program of the form:
with the objective to maximize the marked vertices while adhering to the independence constraint.
Alternatively, a problem formulation commonly used in physics literature expresses this program in terms of a Hamiltonian thatincludes a soft penalty to non-independent configurations (that is when two vertices in the set are connected by an edge) to model the hard independence constraint. This Hamiltonian is given by
with a negative sign in front of the first term because the largest independent set is searched for within an energy minimization problem, and where the penalty parameter V > 1 enforces the constraints.
Energetically, this Hamiltonian favors having each variable in the state xi = 1 unless a pair of vertices are connected by an edge. This second unconstrained formulation provides a straightforward connection to Rydberg atom arrays. Specifically, by mappingthe binary variables xi to two-level Rydberg atoms, MIS-UD problems can be encoded efficiently with Rydberg atoms placed at the vertices of the target problem graph. Strong Rydberg interactions between atoms (as described by the second term in the Hamiltonian) then prevent two neighboring atoms from being simultaneously in the excited Rydberg state.Using a coherent drive with Rabi frequency and detuning , one can then search for the ground state of the Hamiltonian H (encoding the MIS) via, for example, quantum-annealing-type approaches. Compare this blog post for more details on annealing-type quantum optimization algorithms running on Rydberg hardware.
To assess the practical hardness of the MIS-UD problem and compare the performance of various algorithms, we consider the following key figures of merit:
In our work, we studied the MIS-UD problem described earlier using both exact and heuristic algorithms. Here we provide a brief overview of our tool suite for more technical details we refer to Ref. [1].
We now turn to our numerical results. Here we will highlight just a few selected results for more details we refer to Ref. [1].
TTS as function of system size. First, we study TTS as a function of system size (given by the number of nodes in the graph). Our results are displayed in Fig. 2. We find that typical quasi-planar instances with Union-Jack-like connectivity (as studied in Ref. [2]) can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. For most instances (taken as 98th percentile) we can upper-bound the TTS needed by classical B&B or SA solvers through a runtime scaling of the form TTS = O(2aN); we find a = 0.0045 and a = 0.0128 for our B&B and SA solvers, respectively; these resultsset an interesting, putative bar for quantum algorithms to beat. In addition, we observe a relatively large spreadspanning several orders of magnitude in TTS, displaying significant instance-to-instance variations, even for fixed system size, thus motivating a more detailed analysis of problem hardness, as discussed next.
Figure 2. TTS as a function of system size. (Left) B&B solver: Problems with hundreds (thousands) of nodes can be solved to optimality in subsecond (minute) timescales. The solid line is the linear regression over instances whose TTS are in the highest 2%. (Right) SA solver: Time required to reach 99% success probability for the heuristic SA solver as a function of system size (how long the solver should run for a 99% chance of finding the optimal solution). For every system size, 1000 random UD instances have been considered.
Hardness parameter.We now consider algorithmic performance in terms of the hardness parameter HP that accounts for both the degeneracy of the ground as well as first excited states. Our resultsfor both the exact SLA as well as the heuristic SA solvers are displayed in Fig 3., showing a remarkably different behavior. The SA solver displays a strong dependence on the hardness parameter. Conversely, virtually no dependence is observed for the exact SLA solver, thereby demonstrating that the conductance-like hardness parameter HP successfully captures hardness for algorithms undergoing Markov-chain dynamics, while alternative algorithmic paradigms (like sweeping line) may require a different notion of hardness.
In particular, we find that for the SA solver the success probability PMIS fits well to the functional form PMIS=1-exp(-C HPa), where C refers to a positive fitted constant and smaller values of a yield larger success rate. We find 0.66 for our implementation of SA, competitive with a=0.63 as reported for the optimized quantum algorithm demonstrated in Ref. [2] (for smaller systems than studied here, and when restricting the analysis to graphs with minimum energy gaps sufficiently large to be resolved in the duration of the noisy quantum evolution). This is much better than the SA baseline results in Ref. [2] with 1.03. As such, the quantum speedup reported in Ref. [2] could be classified as limited sequential quantum speedup, based on comparing a quantum annealing type algorithm with a particular implementation of classical SA, while our analysis points at a potential next milestone, in the form of the experimental demonstration of a (more general) limited non-tailored quantum speedup, by comparing the performance of the quantum algorithm to the best-known generic classical optimization algorithm.
Figure 3. Dependence on hardness parameter HP (for different system sizes, for lattices with side length L=13 and about 135 nodes up to lattices with L=33 and about 870 nodes). (Left) Time-to-solution (TTS) for the exact SLA solver as a function of the hardness parameter HP. Virtually no dependence on HP is observed, showing that TTS is fully determined by the system size N~L^2. (Right) Conversely, for the Markov-chain based SA solver, we observe a strong correlation between algorithmic performance and the hardness parameter HP. Here we plot log(1 P_MIS), for UD graphs selected from the top two percentile of hardness parameter for each system size. Power-law fits to the form ~HP^(-a) are used to extract scaling performance with graph hardness.
Tuning problem hardness. We now study hardness as we gradually change the topology of the problem instances. Specifically, we analyze TTS following two protocols by either (i) systematically tuning the blockade radius or (ii) randomly rewiring edges of the graph. While protocol (i) prepares UD graphs (with varying connectivity), protocol (ii) explicitly breaks the UD structure via random (potentially long-range) interactions, ultimately preparing random structure-less Erds-Rnyi (ER) graphs. The results of this analysis are shown in Fig. 4. We find that TTS for the established B&B solver can be tuned systematically over several orders of magnitude. As such, these two protocols suggest a potential recipe to benchmark quantum algorithms on instances orders of magnitude harder for established classical solvers than previously studied, and motivate interesting future experiments towards quantum advantage; in particular, our protocols help identify small, but hard instances, as needed for thorough scaling analyses.
Figure 4. Hardness transition. (Left) Hardness transition as a function of the disk radius (in units of the lattice spacing), as given by the time-to-solution (TTS) for the B&B solver, shown here for systems with about 350 nodes, with 100 random seeds per radius. (Right) Hardness transition from unit-disk to random Erds-Rnyi (ER) graphs (denoted by the red shaded bands). Here TTS is given as a function of the fraction of edges rewired. Starting from Union-Jack-type UD graphs (left), edges are randomly selected and rewired, thereby gradually breaking the UD connectivity, and ultimately generating random ER graphs (right). While the original UJ graphs can be solved to optimality in ~10^(-2)s, we observe TTS potentially orders of magnitudes larger in both plots.
Our work provides an in-depth look into the hardness of themaximum independent set problem on unit-disk graphs, the problem native toRydberg atom arrays. Our results establish well-defined goal posts for quantum algorithms to beat. In particular, we have shown that the hardness parameter put forward in Ref. [2] captures problem hardness for a certain class of Markov chain Monte Carlo solvers, while virtually no dependence between time-to-solution and this parameter is observed for alternative solvers. Finally, we have identified protocols to systematically tune time-to-solution over several orders of magnitude, pinpointing problem instancesorders of magnitude harder for established classical solvers than previously studied.
These results should help identify the most promising directions for applications of Rydberg devices and direct the communitys on-going efforts towards quantum advantage, hopefully inspiring many interesting future experiments further exploring the hardness of the MIS problem with Rydberg atom arrays.
The content and opinions in this blog are those of the third-party author and AWS is not responsible for the content or accuracy of this blog.
Thisblogpost is for informational purposes only and is not intended as legal, tax, financial, investment, accounting or regulatory advice. Opinions expressed herein are the personal views of the individual(s) and do not represent the views of JPMorgan Chase & Co. The accuracy of any statements, linked resources, reported findings or quotations is not the responsibility of JPMorgan Chase & Co.
[1]R. S. Andrist, M. J. A. Schuetz, P. Minssen, R. Yalovetzky, S. Chakrabarti, D. Herman, N. Kumar, G. Salton, R. Shaydulin, Y. Sun, M. Pistoia, and H. G. Katzgraber, Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups, Phys. Rev. Research 5, 043277 (2023); arXiv:2307.09442.
[2]S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, et al., Quantum optimization of Maximum Independent Set using Rydberg atom arrays, Science 376, 1209 (2022).
[3]J. Wurtz, P. L. S. Lopes, N. Gemelke, A. Keesling, and S. Wang, Industry applications of neutral-atom quantum computing solving Independent Set problems, arXiv:2205.08500 (2022).
Read the original post:
JPMorgan Chase and AWS study the prospects for quantum speedups with near-term Rydberg atom arrays | Amazon ... - AWS Blog
- Mathematician breaks down how to defend against quantum ... - Phys.Org [Last Updated On: February 28th, 2017] [Originally Added On: February 28th, 2017]
- Here Is Everything You Need to Know About Quantum Computers - Interesting Engineering [Last Updated On: March 18th, 2017] [Originally Added On: March 18th, 2017]
- Quantum Computing Market Forecast 2017-2022 | Market ... [Last Updated On: March 18th, 2017] [Originally Added On: March 18th, 2017]
- What is Quantum Computing? Webopedia Definition [Last Updated On: March 18th, 2017] [Originally Added On: March 18th, 2017]
- Quantum computing is about to disrupt the government contracts market - Bloomberg Government (blog) [Last Updated On: April 22nd, 2017] [Originally Added On: April 22nd, 2017]
- Scientists: We Have Detected the Existence of a Fundamentally New State of Matter - Futurism [Last Updated On: April 22nd, 2017] [Originally Added On: April 22nd, 2017]
- What Sorts Of Problems Are Quantum Computers Good For? - Forbes [Last Updated On: April 22nd, 2017] [Originally Added On: April 22nd, 2017]
- quantum computing - WIRED UK [Last Updated On: April 22nd, 2017] [Originally Added On: April 22nd, 2017]
- Inside Microsoft's 'soup to nuts' quantum computing ramp-up - Computerworld Australia [Last Updated On: April 29th, 2017] [Originally Added On: April 29th, 2017]
- Molecular magnets closer to application in quantum computing - Next Big Future [Last Updated On: May 15th, 2017] [Originally Added On: May 15th, 2017]
- The Bizarre Quantum Test That Could Keep Your Data Secure - WIRED [Last Updated On: May 18th, 2017] [Originally Added On: May 18th, 2017]
- IBM boosts power of quantum computing processors as it lays ... - www.computing.co.uk [Last Updated On: May 22nd, 2017] [Originally Added On: May 22nd, 2017]
- IBM makes leap in quantum computing power - ITworld [Last Updated On: May 22nd, 2017] [Originally Added On: May 22nd, 2017]
- Toward mass-producible quantum computers | MIT News - MIT News [Last Updated On: June 2nd, 2017] [Originally Added On: June 2nd, 2017]
- Purdue, Microsoft Partner On Quantum Computing Research | WBAA - WBAA [Last Updated On: June 2nd, 2017] [Originally Added On: June 2nd, 2017]
- Tektronix AWG Pulls Test into Era of Quantum Computing - Electronic Design [Last Updated On: June 2nd, 2017] [Originally Added On: June 2nd, 2017]
- Google to Achieve "Supremacy" in Quantum Computing by the End of 2017 - Big Think [Last Updated On: July 1st, 2017] [Originally Added On: July 1st, 2017]
- Quantum Computing Becomes More Accessible - Scientific American [Last Updated On: July 1st, 2017] [Originally Added On: July 1st, 2017]
- Qudits: The Real Future of Quantum Computing? - IEEE Spectrum - IEEE Spectrum [Last Updated On: July 1st, 2017] [Originally Added On: July 1st, 2017]
- Alkermes and IBM's quantum computing. Who'll be the big winner? Malcolm Berko - Durham Herald Sun [Last Updated On: July 6th, 2017] [Originally Added On: July 6th, 2017]
- Quantum Computers Made Even More Powerful with New microchip generating 'Qudits' - TrendinTech [Last Updated On: July 8th, 2017] [Originally Added On: July 8th, 2017]
- Quantum Computing Record Broken - Wall Street Pit [Last Updated On: July 8th, 2017] [Originally Added On: July 8th, 2017]
- Technique for measuring and controlling electron state is a ... - UCLA Newsroom [Last Updated On: July 9th, 2017] [Originally Added On: July 9th, 2017]
- Quantum cheques could be a forgery-free way to move money - New Scientist [Last Updated On: July 10th, 2017] [Originally Added On: July 10th, 2017]
- Quantum-computer node uses two different ion species - physicsworld.com [Last Updated On: July 10th, 2017] [Originally Added On: July 10th, 2017]
- Quantum Computers vs Bitcoin How Worried Should We Be? - The Merkle [Last Updated On: July 10th, 2017] [Originally Added On: July 10th, 2017]
- Why you might trust a quantum computer with secretseven over ... - Phys.Org [Last Updated On: July 12th, 2017] [Originally Added On: July 12th, 2017]
- Physicists Take Big Step Towards Quantum Computing and ... - Universe Today [Last Updated On: August 1st, 2017] [Originally Added On: August 1st, 2017]
- Quantum Computing Market Worth 495.3 Million USD by 2023 | 08 ... - Markets Insider [Last Updated On: August 10th, 2017] [Originally Added On: August 10th, 2017]
- China uses a quantum satellite to transmit potentially unhackable data - CNBC [Last Updated On: August 10th, 2017] [Originally Added On: August 10th, 2017]
- Blind quantum computing for everyone - Phys.org - Phys.Org [Last Updated On: August 12th, 2017] [Originally Added On: August 12th, 2017]
- Quantum Computing Is Real, and D-Wave Just Open ... - WIRED [Last Updated On: August 12th, 2017] [Originally Added On: August 12th, 2017]
- Machine learning tackles quantum error correction - Phys.Org [Last Updated On: August 15th, 2017] [Originally Added On: August 15th, 2017]
- Quantum Internet Is 13 Years Away. Wait, What's Quantum Internet? - WIRED [Last Updated On: August 15th, 2017] [Originally Added On: August 15th, 2017]
- Physicists Have Made Exotic Quantum States From Light - Futurism [Last Updated On: August 16th, 2017] [Originally Added On: August 16th, 2017]
- $495.3 Million Quantum Computing Market 2017 by Revenue Source, Application, Industry, and Geography - Global ... - PR Newswire (press release) [Last Updated On: August 18th, 2017] [Originally Added On: August 18th, 2017]
- How quantum mechanics can change computing - The Conversation US [Last Updated On: August 23rd, 2017] [Originally Added On: August 23rd, 2017]
- Introducing Australia's first quantum computing hardware company - Computerworld Australia [Last Updated On: August 23rd, 2017] [Originally Added On: August 23rd, 2017]
- IEEE Approves Standards Project for Quantum Computing ... - insideHPC [Last Updated On: August 23rd, 2017] [Originally Added On: August 23rd, 2017]
- Commonwealth Bank investing in Australia's first quantum computer company - Which-50 (blog) [Last Updated On: August 25th, 2017] [Originally Added On: August 25th, 2017]
- How quantum mechanics can change computing - San Francisco ... - San Francisco Chronicle [Last Updated On: August 25th, 2017] [Originally Added On: August 25th, 2017]
- Quantum Computing Is Coming at Us Fast, So Here's Everything You Need to Know - ScienceAlert [Last Updated On: August 27th, 2017] [Originally Added On: August 27th, 2017]
- Quantum computing event explores the implications for business - Cambridge Network [Last Updated On: August 30th, 2017] [Originally Added On: August 30th, 2017]
- Microsoft's Aussie quantum computing lab set to scale up next-gen ... - ARNnet [Last Updated On: September 7th, 2017] [Originally Added On: September 7th, 2017]
- An Entirely New Type of Quantum Computing Has Just Been Invented - Futurism [Last Updated On: September 7th, 2017] [Originally Added On: September 7th, 2017]
- Microsoft just upped its multi-million bet on quantum computing - ZDNet [Last Updated On: September 7th, 2017] [Originally Added On: September 7th, 2017]
- Here's what quantum computing is and why it matters [Last Updated On: October 6th, 2017] [Originally Added On: October 6th, 2017]
- What will you actually use quantum computing for? | ZDNet [Last Updated On: October 11th, 2017] [Originally Added On: October 11th, 2017]
- Quantum Computing | Intel Newsroom [Last Updated On: October 13th, 2017] [Originally Added On: October 13th, 2017]
- Intel Takes First Steps To Universal Quantum Computing [Last Updated On: October 13th, 2017] [Originally Added On: October 13th, 2017]
- Qudits: The Real Future of Quantum Computing? - IEEE Spectrum [Last Updated On: October 13th, 2017] [Originally Added On: October 13th, 2017]
- quantum computing - engadget.com [Last Updated On: October 13th, 2017] [Originally Added On: October 13th, 2017]
- Quantum computing - news.microsoft.com [Last Updated On: November 1st, 2017] [Originally Added On: November 1st, 2017]
- IBM's processor pushes quantum computing ... - engadget.com [Last Updated On: November 16th, 2017] [Originally Added On: November 16th, 2017]
- Yale Professors Race Google and IBM to the First Quantum ... [Last Updated On: November 16th, 2017] [Originally Added On: November 16th, 2017]
- Quantum Computing Is the Next Big Security Risk | WIRED [Last Updated On: December 8th, 2017] [Originally Added On: December 8th, 2017]
- Microsoft offers developers a preview of its quantum ... [Last Updated On: December 12th, 2017] [Originally Added On: December 12th, 2017]
- New silicon structure opens the gate to quantum computers [Last Updated On: December 14th, 2017] [Originally Added On: December 14th, 2017]
- Quantum Computing Explained | What is Quantum Computing? [Last Updated On: December 21st, 2017] [Originally Added On: December 21st, 2017]
- What is Quantum Computing? | SAP News Center [Last Updated On: December 23rd, 2017] [Originally Added On: December 23rd, 2017]
- Is Quantum Computing an Existential Threat to Blockchain ... [Last Updated On: December 25th, 2017] [Originally Added On: December 25th, 2017]
- IBM puts its quantum computer to work in relaxing, nerdy ASMR ... [Last Updated On: January 8th, 2018] [Originally Added On: January 8th, 2018]
- Quantum computing is going to change the world. Here's what ... [Last Updated On: January 8th, 2018] [Originally Added On: January 8th, 2018]
- The Era of Quantum Computing Is Here. Outlook: Cloudy ... [Last Updated On: January 26th, 2018] [Originally Added On: January 26th, 2018]
- What is quantum computing? - Definition from WhatIs.com [Last Updated On: February 5th, 2018] [Originally Added On: February 5th, 2018]
- Senate bills would make quantum computing a priority [Last Updated On: June 10th, 2018] [Originally Added On: June 10th, 2018]
- Two Quantum Computing Bills Are Coming To Congress [Last Updated On: July 5th, 2018] [Originally Added On: July 5th, 2018]
- Quantum Computing Market Research Report- Forecast 2022 | MRFR [Last Updated On: August 1st, 2018] [Originally Added On: August 1st, 2018]
- What Is Quantum Computing? The Complete WIRED Guide | WIRED [Last Updated On: August 22nd, 2018] [Originally Added On: August 22nd, 2018]
- Quantum Computing | USRA [Last Updated On: August 30th, 2018] [Originally Added On: August 30th, 2018]
- The quantum computing race the US cant afford to lose [Last Updated On: September 3rd, 2018] [Originally Added On: September 3rd, 2018]
- The reality of quantum computing could be just three years ... [Last Updated On: September 12th, 2018] [Originally Added On: September 12th, 2018]
- US takes first step toward a quantum computing workforce ... [Last Updated On: September 17th, 2018] [Originally Added On: September 17th, 2018]
- China bet big on quantum computing. Now the ... - money.cnn.com [Last Updated On: September 17th, 2018] [Originally Added On: September 17th, 2018]
- China bet big on quantum computing. Now the US races to ... [Last Updated On: October 26th, 2018] [Originally Added On: October 26th, 2018]
- A new type of quantum computer has smashed every record ... [Last Updated On: December 21st, 2018] [Originally Added On: December 21st, 2018]
- IBM unveils its first commercial quantum computer [Last Updated On: January 9th, 2019] [Originally Added On: January 9th, 2019]
- IBM thinks outside of the lab, puts quantum computer in a box [Last Updated On: January 11th, 2019] [Originally Added On: January 11th, 2019]
- Quantum Computing | The MIT Press [Last Updated On: January 11th, 2019] [Originally Added On: January 11th, 2019]
- CES 2019: IBM's Q System One Is the Rock Star Quantum ... [Last Updated On: January 13th, 2019] [Originally Added On: January 13th, 2019]