AWS Quantum Technologies Blog

AWS and JPMorganChase collaborate to advance quantum computing R&D

This post was contributed by Martin Schuetz and Ruben Andrist from the Amazon Advanced Solutions Lab, and Romina Yalovetzky and Atithi Acharya from Global Technology Applied Research at JPMorganChase.

Quantum researchers at JPMorganChase and the Amazon Advanced Solutions Lab are working together to explore how quantum technologies may help address complex optimization problems in finance and beyond. This sustained, multi-project research program has enabled shared methodologies and co-designed algorithms and experiments, deepening our understanding of how quantum and classical resources can work together in practice.

We developed a novel hybrid (quantum-classical) approach for solving large-scale graph optimization problems, validated and tested through experiments on Amazon Braket. We used quantum devices as co-processors to augment advanced classical solvers, benchmark results on systems available today on Amazon Braket, and shape future experiments.

In this post, we share some highlights from our collaboration. You’ll learn how we: 1. Built a decomposition pipeline that reduces portfolio optimization problems by ~80%, making them small enough for near-term quantum hardware. 2. Developed a compilation toolkit that has the potential to shrink qubit requirements by orders of magnitude for real-world graph problems. 3. Created qReduMIS, a hybrid algorithm where quantum devices serve as co-processors to classical solvers – achieving above ~89% average success rates on hard problem instances using QuEra’s Aquila device on Amazon Braket.

A Suite of Tools for Near-Term Quantum Hardware

Combinatorial optimization problems are ubiquitous across different areas in industry and science, with prominent examples in areas like transportation and logistics, telecommunications, manufacturing, and finance. Analog neutral-atom quantum machines based on Rydberg atoms 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.

In previous work we studied the computational hardness of certain optimization problems, inspired by real-world use cases in finance (see our blog post here). With a deeper understanding for problem hardness and quantum speedups, our collaboration has then produced three additional research papers that together provide a comprehensive toolkit for solving large-scale optimization problems on near-term Rydberg quantum hardware. Here we will provide an overview of our results – for more details we refer to our original publications in Refs. [1-3].

  1. Decomposition Pipeline for Portfolio Optimization [1]
Figure 1. Schematic overview of our decomposition pipeline for solving large optimization problems. The objective is denoted by H, and the constraint set is denoted by Ω. Decompose: We first preprocess the correlation matrix using Random Matrix Theory (RMT). The resulting problem is then partitioned into a series of subproblems using community detection methods. Solve: Each subproblem is solved (in parallel). Aggregate: The subproblems are aggregated and post-processed for feasibility checks into the final solution x*. Finally, we check the final objective value, while ensuring feasibility.

Figure 1. Schematic overview of our decomposition pipeline for solving large optimization problems. The objective is denoted by H, and the constraint set is denoted by Ω. Decompose: We first preprocess the correlation matrix using Random Matrix Theory (RMT). The resulting problem is then partitioned into a series of subproblems using community detection methods. Solve: Each subproblem is solved (in parallel). Aggregate: The subproblems are aggregated and post-processed for feasibility checks into the final solution x*. Finally, we check the final objective value, while ensuring feasibility.

The first paper [1] addresses the challenge of solving industrially relevant constrained optimization problems, such as portfolio optimization and rebalancing, which are often intractable or difficult to solve exactly. We propose and benchmark a decomposition pipeline that can break large-scale problems down into smaller, more manageable subproblems, with implications for both classical and quantum computation. See Figure 1 for a schematic illustration.

Our empirical results show that our pipeline consistently reduces the size of real-world portfolio optimization problems by approximately 80%, while maintaining solution quality within a minimal error. We further report on a 3x reduction in time-to-solution for large-scale portfolio optimization problems with up to 1500 variables. The pipeline decomposes the optimization problem into constrained subproblems, which are then solved separately and aggregated to give a final result. By leveraging the underlying structure present in financial data and using random matrix theory to clean correlation matrices, we can use modified community detection algorithms to identify subproblems.

Moreover, by decomposing large problems into several smaller subproblems, the pipeline allows us to embed these smaller subproblems onto near-term quantum devices with hundreds of qubits, thus enabling the use of near-term quantum devices as solvers, and providing a path toward practical utility of quantum computers in portfolio optimization.

  1. Quantum Compilation Toolkit for Rydberg Atom Arrays [2]
Figure 2. Schematic illustration of our compilation for solving the Maximum Independent Set (MIS) problem on large graphs using Rydberg atom arrays. The process begins with an arbitrary input graph (e.g., the Cora citation graph with ~2700 nodes and ~5300 edges) generically incompatible with the connectivity constraints of Rydberg quantum hardware. Through deterministic reduction algorithms, the graph is reduced (exactly, without approximation) to a smaller kernel—reducing Cora to just 9 nodes and 12 edges. A compatibility checker then verifies whether the reduced graph meets hardware constraints based on properties like maximum degree and triangle count. Finally, our embedding algorithms map the logical graph onto physical Rydberg hardware with limited connectivity (e.g., a lattice with union-jack connectivity). The embedding is optimized to minimize overhead, and quantum wires with ancilla atoms are used to introduce missing connections. For Cora, this yields a hardware-native embedding with just 9 nodes, 11 edges, and 8 ancilla atoms in a quantum wire.

Figure 2. Schematic illustration of our compilation for solving the Maximum Independent Set (MIS) problem on large graphs using Rydberg atom arrays. The process begins with an arbitrary input graph (e.g., the Cora citation graph with ~2700 nodes and ~5300 edges) generically incompatible with the connectivity constraints of Rydberg quantum hardware. Through deterministic reduction algorithms, the graph is reduced (exactly, without approximation) to a smaller kernel—reducing Cora to just 9 nodes and 12 edges. A compatibility checker then verifies whether the reduced graph meets hardware constraints based on properties like maximum degree and triangle count. Finally, our embedding algorithms map the logical graph onto physical Rydberg hardware with limited connectivity (e.g., a lattice with union-jack connectivity). The embedding is optimized to minimize overhead, and quantum wires with ancilla atoms are used to introduce missing connections. For Cora, this yields a hardware-native embedding with just 9 nodes, 11 edges, and 8 ancilla atoms in a quantum wire.

The second paper [2] proposes and implements a comprehensive quantum compilation toolkit for solving the maximum independent set (MIS) problem on quantum hardware based on Rydberg atom arrays. Our end-to-end pipeline involves three core components to efficiently map generic MIS instances onto Rydberg arrays with unit-disk connectivity, with modules for graph reduction, hardware compatibility checks, and graph embedding; see Figure 2 for illustration.

The first module (reducer) provides hardware-agnostic and deterministic reduction logic that iteratively reduces the problem size via (exact) lazy clique removals. We find that real-world networks can typically be reduced by orders of magnitude on subsecond timescales, thus significantly cutting down the eventual load for quantum devices. For example, consider the real-world Cora citation graph with approximately 2,700 nodes. To embed this graph on Rydberg hardware using previous methods would require approximately 29 million qubits, far beyond the capabilities of near-term quantum hardware. Leveraging exact graph reduction techniques together with an optimized embedding scheme, we show that this graph can in fact be encoded with tens of qubits, thus reducing the required qubit overhead by orders of magnitude and enabling the use of near-term quantum devices.

The second module (compatibility checker) implements a hardware compatibility checker that quickly determines whether a given input graph may be compatible with the restrictions imposed by Rydberg quantum hardware. The third module (embedder) describes hardware-efficient graph embedding routines to generate approximate encodings with controllable overhead and optimized ancilla placements. We exemplify our pipeline with experiments run on the QuEra Aquila device available on Amazon Braket.

  1. qReduMIS: A Quantum-Informed Reduction Algorithm [3]
Figure 3. The hybrid qReduMIS framework consists of three layers: (i) application, (ii) algorithm, and (iii) hardware. The application layer is illustrated using a portfolio selection problem (PSP) that can be formulated as a MIS problem on an asset graph. For a given graph G, the qReduMIS algorithm solves the MIS problem by combining exact polynomial-time reduction logic with quantum measurement data to identify and remove frozen vertices with high or low likelihood of being part of large independent sets, thereby unblocking the kernelization process. The framework is hardware-agnostic and compatible with both digital and analog quantum devices, including Rydberg atom arrays implementing analog Hamiltonian simulation (AHS) programs.

Figure 3. The hybrid qReduMIS framework consists of three layers: (i) application, (ii) algorithm, and (iii) hardware. The application layer is illustrated using a portfolio selection problem (PSP) that can be formulated as a MIS problem on an asset graph. For a given graph G, the qReduMIS algorithm solves the MIS problem by combining exact polynomial-time reduction logic with quantum measurement data to identify and remove frozen vertices with high or low likelihood of being part of large independent sets, thereby unblocking the kernelization process. The framework is hardware-agnostic and compatible with both digital and analog quantum devices, including Rydberg atom arrays implementing analog Hamiltonian simulation (AHS) programs.

The third paper [3] introduces qReduMIS, a hybrid quantum-classical algorithm for the maximum independent set (MIS) problem. Here, we use a quantum computer as a co-processor that feeds information back into classical reduction logic. Specifically, quantum measurement data identifies frozen vertices that are highly likely (or unlikely) to appear in large independent sets. Removing these vertices unblocks further classical kernelization, creating a recursive loop where quantum and classical resources reinforce each other. See Figure 3 for a schematic illustration of the qReduMIS framework.

Figure 4. Success probability PMIS as a function of the hardness parameter H, for QAA (red squares), classical SA (bright blue diamonds), qReduMIS (blue circles), and a random-informed baseline (black triangles). Error bars refer to 90% confidence intervals as extracted via bootstrapping; for SA error bars are estimated via repeated Bernoulli experiments. The inset provides selected results for those nine instances (with a non-zero kernel) that are not solved by classical reduction alone.

Figure 4. Success probability PMIS as a function of the hardness parameter H, for QAA (red squares), classical SA (bright blue diamonds), qReduMIS (blue circles), and a random-informed baseline (black triangles). Error bars refer to 90% confidence intervals as extracted via bootstrapping; for SA error bars are estimated via repeated Bernoulli experiments. The inset provides selected results for those nine instances (with a non-zero kernel) that are not solved by classical reduction alone.

We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on QuEra’s Aquila quantum device available through Amazon Braket. Our results are displayed in Figure 4. For quantum annealing algorithms (QAA) the success rate PMIS is strongly suppressed for hard instances, dropping to small PMIS ≳ 0 for most (hard) instances with hardness H ≳ 10. While more performant than QAA, we observe a similar performance drop for classical simulated annealing (SA) [4]. Conversely, qReduMIS solves most instances to optimality with PMIS = 1 and maintains a non-zero success rate with average PMIS ≳ 89% throughout our testbed. Overall, these results illustrate the benefits of introducing kernelization techniques over both classical and quantum Markov-chain Monte Carlo-based methods.

Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices, given by the exponential performance suppression in the conductance-like hardness parameter for hard MIS problem instances.

Looking Ahead

Together, our three papers provide a comprehensive suite of tools that extends the class of problems that can be tackled with near-term Rydberg atom arrays and help push the art of the possible for Rydberg quantum devices (as available on Amazon Braket through the QuEra Aquila device). Our results should help identify the most promising directions for applications of Rydberg devices and direct the community’s ongoing efforts towards quantum advantage, hopefully inspiring many interesting future experiments.

If you’re interested in exploring these techniques for your own optimization challenges, reach out to the Amazon Advanced Solutions Lab.

References

[1] A. Acharya, R. Yalovetzky, P. Minssen, S. Chakrabarti, R. Shaydulin, R. Raymond, Y. Sun, D. Herman, R. S. Andrist, G. Salton, M. J. A. Schuetz, H. G. Katzgraber, and M. Pistoia, Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing, Phys. Rev. Research 7, 023142 (2025); arXiv:2409.10301.

[2] M. J. A. Schuetz, R. S. Andrist, G. Salton, R. Yalovetzky, R. Raymond, Y. Sun, A. Acharya, S. Chakrabarti, M. Pistoia, and H. G. Katzgraber, Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups, Phys. Rev. Research 7, 033107 (2025); arXiv:2412.14976.

[3] M. J. A. Schuetz, R. Yalovetzky, R. S. Andrist, G. Salton, Y. Sun, R. Raymond, S. Chakrabarti, A. Acharya, R. Shaydulin, M. Pistoia, and H. G. Katzgraber, qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem, arXiv:2503.12551.

[4] 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.