Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Frontiers in Optics

Classical Machines, for Solving the Toughest Problems in Computer Science

Eli Yablonovitch, Tianyao Patrick Xiao, Sri Krishna Vadlamani

Published Jan 1, 2019• 0 citations
Publisher

Abstract

Classical analog processors are now solving hard Computer Science problems that were thought to require a Quantum Computer. There are now classical machines that solve Ising type optimizations, opening the door toward other NP-hard problems as well.
DOI
10.1364/fio.2019.jtu4a.114

Related papers

Quantum Computing: Solving Complex Problems

David Peter Divincenzo

One of the motivating ideas of quantum computation was that there could be a new kind of machine that would solve hard problems in quantum mechanics. There has been significant progress towards the experimental realization of these machines (which I will review), but there are still many questions about how such a machine could solve computational problems of interest in quantum physics. New categorizations of the complexity of computational problems have now been invented to describe quantum simulation. The bad news is that some of these problems are believed to be intractable even on a quantum computer, falling into a quantum analog of the NP class. The good news is that there are many other new classifications of tractability that may apply to several situations of physical interest.

•Apr 11, 2007•0 citations

Quantum Breakthrough

Soorena Merat, Wahab Almuhtadi

Analog computers have a rich history and have been used for centuries to solve complex problems. Unlike digital computers, they operate on continuous data. This unique approach is found in everything from early mechanical calculators to specialized encryption devices. The core idea is to split a significant problem into smaller, independent tasks that can be solved simultaneously by multiple processors/cores. Think of it as many cooks in a kitchen working on different dishes for a meal.

CRC Press eBooks•Apr 11, 2025•0 citations

Equation Planting: A Tool for Benchmarking Ising Machines

Itay Hen

Recent years have witnessed the flourishing of experimental $I\phantom{\rule{0}{0ex}}s\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$ $m\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}c\phantom{\rule{0}{0ex}}h\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}s$, special-purpose computational devices that promise to solve the world's toughest optimization problems in record times. Evaluating an Ising machine's performance is problematic, though, as it poses two seemingly contradictory requirements: On the one hand, the generated problem instances should be hard to solve, yet on the other hand they should have verifiable solutions. This study provides a methodology for generating random optimization-problem sets from linear systems of equations that possess both desired properties, thereby allowing direct, unbiased benchmarking of these physical optimization devices.

arXiv:1903.10928•Physical Review Applied•Jul 19, 2019•24 citations

Optimal solving of a binary knapsack problem on a D-Wave quantum machine and its implementation in production systems

Wojciech Bożejko, Anna Burduk, Jarosław Pempera +2 more

Abstract The efficient management of complex production systems is a challenge in today’s logistics. In the field of intelligent and sustainable logistics, the optimization of production batches, especially in the context of a rapidly changing product range, requires fast and precise computational solutions. This paper explores the potential of quantum computers for solving these problems. Traditional computational methods are often limited when it comes to optimizing complex logistics systems. In response to these challenges, the paper proposes the use of a hybrid algorithm that combines quantum technologies with classical computational methods. Such integration allows the computational power of both types of technologies to be harnessed, leading to faster and more efficient identification of optimal solutions. In this work, we consider the knapsack problem, a classic NP-hard optimization problem that is commonly used to verify the effectiveness of new algorithm construction methods. The algorithm presented is based on the Branch and Bound method and aims to ensure solution optimality in the context of the non-determinism of quantum computers. Within the algorithm, computations are performed alternately on a classical processor and a quantum processor. In addition, the lower and upper bounds of the objective function are computed in constant time using the D-Wave quantum machine.

Annals of Operations Research•May 13, 2024•19 citations

Simulations of Many-Body Quantum Systems by a Quantum Computer

Stephen J. Wiesner

We suggest that quantum computers can solve quantum many-body problems that are impracticable to solve on a classical computer.

arXiv:quant-ph/9603028•Mar 26, 1996•127 citations

Accelerating NP-Hard Optimization via Quantum-Inspired Classical Algorithms

Mukesh Krishnan, Saravanan Dr

A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.

International Innovative Research Journal of Engineering and Technology•Mar 30, 2025•0 citations
One of the motivating ideas of quantum computation was that there could be a new kind of machine that would solve hard problems in quantum mechanics. There has been significant progress towards the experimental realization of these machines (which I will review), but there are still many questions about how such a machine could solve computational problems of interest in quantum physics. New categorizations of the complexity of computational problems have now been invented to describe quantum simulation. The bad news is that some of these problems are believed to be intractable even on a quantum computer, falling into a quantum analog of the NP class. The good news is that there are many other new classifications of tractability that may apply to several situations of physical interest.
Recent years have witnessed the flourishing of experimental $I\phantom{\rule{0}{0ex}}s\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$ $m\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}c\phantom{\rule{0}{0ex}}h\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}s$, special-purpose computational devices that promise to solve the world's toughest optimization problems in record times. Evaluating an Ising machine's performance is problematic, though, as it poses two seemingly contradictory requirements: On the one hand, the generated problem instances should be hard to solve, yet on the other hand they should have verifiable solutions. This study provides a methodology for generating random optimization-problem sets from linear systems of equations that possess both desired properties, thereby allowing direct, unbiased benchmarking of these physical optimization devices.
Abstract The efficient management of complex production systems is a challenge in today’s logistics. In the field of intelligent and sustainable logistics, the optimization of production batches, especially in the context of a rapidly changing product range, requires fast and precise computational solutions. This paper explores the potential of quantum computers for solving these problems. Traditional computational methods are often limited when it comes to optimizing complex logistics systems. In response to these challenges, the paper proposes the use of a hybrid algorithm that combines quantum technologies with classical computational methods. Such integration allows the computational power of both types of technologies to be harnessed, leading to faster and more efficient identification of optimal solutions. In this work, we consider the knapsack problem, a classic NP-hard optimization problem that is commonly used to verify the effectiveness of new algorithm construction methods. The algorithm presented is based on the Branch and Bound method and aims to ensure solution optimality in the context of the non-determinism of quantum computers. Within the algorithm, computations are performed alternately on a classical processor and a quantum processor. In addition, the lower and upper bounds of the objective function are computed in constant time using the D-Wave quantum machine.
A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.