Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints. While significant progress has been made with variational approaches such as QAOA, most problems addressed are unconstrained (such as Max-Cut). In this study, we investigate a hybrid quantum-classical method for constrained optimization problems, particularly those with knapsack constraints that occur frequently in financial and supply chain applications. Our proposed method relies firstly on relaxations to local quantum Hamiltonians, defined through commutative maps. Drawing inspiration from quantum random access code (QRAC) concepts, particularly Quantum Random Access Optimizer (QRAO), we explore QRAO's potential in solving large constrained optimization problems. We employ classical techniques like Linear Relaxation as a presolve mechanism to handle constraints and cope further with scalability. We compare our approach with QAOA and present the final results for a real-world procurement optimization problem: a significant-sized multi-knapsack-constrained problem.
Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints. While significant progress has been made with variational approaches such as QAOA, most problems addressed are unconstrained (such as Max-Cut). In this study, we investigate a hybrid quantum-classical method for constrained optimization problems, particularly those with knapsack constraints that occur frequently in financial and supply chain applications. Our proposed method relies firstly on relaxations to local quantum Hamiltonians, defined through commutative maps. Drawing inspiration from quantum random access code (QRAC) concepts, particularly Quantum Random Access Optimizer (QRAO), we explore QRAO's potential in solving large constrained optimization problems. We employ classical techniques like Linear Relaxation as a presolve mechanism to handle constraints and cope further with scalability. We compare our approach with QAOA and present the final results for a real-world procurement optimization problem: a significant-sized multi-knapsack-constrained problem.
Optimization problems are widely encountered in real-world domains such as energy systems, financial markets, transportation networks, supply chain logistics, manufacturing processes, and e-commerce platforms. Traditional classical computing methods often struggle to solve large combinatorial optimization problems due to the exponential growth of the solution space. Quantum computing has emerged as a promising approach to address these challenges by leveraging quantum mechanical principles such as superposition and entanglement. However, current quantum hardware is limited by noise, restricted qubit availability, and scalability issues, making fully quantum solutions impractical for large-scale applications. To overcome these limitations, this research proposes a hybrid quantum–classical supercomputing framework for solving complex optimization problems across multiple domains. The framework integrates classical data processing and optimization techniques with quantum-inspired algorithms, specifically the Quantum Approximate Optimization Algorithm (QAOA), to efficiently explore large solution spaces. Real-world datasets from energy systems, supply chain logistics, financial markets, transportation networks, manufacturing processes, and e-commerce platforms are used for experimental evaluation. The results demonstrate that the hybrid optimization approach can generate higher-quality solutions and improved optimization accuracy compared to traditional classical methods. These findings highlight the potential of hybrid quantum–classical systems as an effective and scalable solution for solving complex optimization problems in modern computational applications.
Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. Differing from standard quantum optimizers such as QAOA, it utilizes the eigenstates of local quantum Hamiltonians that are not diagonal in the computational basis. There are indications that quantum entanglement may not be needed to solve binary optimization problems with standard quantum optimizers because their maximal eigenstates of diagonal Hamiltonians include classical states. In this study, while quantumness does not always improve the performance of quantum relaxations, we observed that there exist some instances in which quantum relaxation succeeds to find optimal solutions with the help of quantumness. Our results suggest that QRAO not only can scale the instances of binary optimization problems solvable with limited quantum computers but also can benefit from quantum entanglement,
Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at https://github.com/ToyotaCRDL/rqrao.
Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.