Quantum annealing is expected to be a powerful generic algorithm for solving hard com- binatorial optimization problems faster than classical computers. Finding the solution to a combinatorial opti ...
Quantum annealing is expected to be a powerful generic algorithm for solving hard combinatorial optimization problems faster than classical computers. Finding the solution to a combinatorial optimization problem is equivalent to finding the ground state of an Ising Hamiltonian. In today's quantum annealers the spins of the Ising Hamiltonian are mapped to superconducting qubits. On the other hand, dissipation processes degrade the success probability of finding the solution. In this thesis we set out to explore a newly proposed architecture for a noise-resilient quantum annealer that instead maps the Ising spins to continuous variable quantum states of light encoded in the field quadratures of a two-photon pumped Kerr- nonlinear resonator based on the proposal by Puri et al. (2017). In this thesis we study the Wigner negativity for this newly proposed architecture and evaluate its performance based on the negativity of the Wigner function. We do this by determining an experimental value to when the presence of losses become too detrimental, such that the Wigner function of the quantum state during the evolution within the anneal becomes positive for all times. Furthermore, we also demonstrate the capabilities of this continuous variable quantum annealer by simulating and finding the best solution of a small instance of the NP-complete subset sum problem and of the number partitioning problem.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing. We also present preliminary results about the application of quantum dissipation (as an alternative to imaginary time evolution) to the task of driving a quantum system toward its state of lowest energy.
Optimization deals with problem of finding the minimum of a given cost function (the relationship between the total cost of production and the quantity of a product produced) and in the combinatorial optimisation problems the cost function depends on a large number of variables and hard problems are those for which the computational time is not bound by any polynomial in the problem size [1]. To solve hard optimization problems is a challenging task. Several techniques have been developed to get to the solution(s) of such problems. Here we will discuss about some of the problems and also the techniques that have already been implemented.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.