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

Quantum Computing: Solving Complex Problems

David Peter Divincenzo

Published Apr 11, 2007• 0 citations
Publisher

Abstract

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.

DOI
10.1007/978-3-540-74559-4_12

Related papers

Quantum Computing: Unleashing the Power of Efficient Problem Solving

Sadaquat Ali Ruk, Maham Shahid, Areeba Raees +1 more

Quantum computing aims to outperform classical computers for some specific calculations. It relies on the additional resources given by the qubit superposition states, which can be used to design more efficiently. Reversibility of quantum computation may help in solving NP problems, which are easy in one direction but hard in the opposite sense. Quantum computers can enhance data processing and analysis tasks. The potential impact of quantum algorithms on optimization problems, simulation of quantum systems, and machine learning tasks such as clustering and classification. It also includes efforts to standardize quantum hardware and software interfaces, enabling interoperability and accelerating the adoption of quantum computing. The barriers we face while adopting Quantum computing are the accuracy of the information, lack of technical experts, and organizational interest in adopting the new process. We find one more critical barrier is the lack of standards of secure communication techniques while adopting quantum computing. While numerous challenges lie ahead, the promise of quantum computing in solving complex problems and driving innovation is too significant to ignore. We will examine the existing quantum algorithms and applications that have demonstrated quantum advantage or potential utility in various domains. The quantum computing field is expected to transition from physical qubits to error-corrected logical qubits. AI is likely to be unleashed by quantum computing for formidable progress advances in speed, cost, and algorithm learning function. Quantum computing solves one or two problems, with little practical use, and costs a fortune to run. Additionally, we will assess the challenges associated with scaling up quantum systems, addressing the issues of quantum coherence, error correction, and noise reduction.

Journal of Interdisciplinary Innovational Letters•Dec 31, 2024•0 citations

Quantum computing: promises, achievements and challenges

Thomas Ayral

Quantum computers regularly make the headlines, with optimistic claims (often issued by companies large and small) alternating with pessimistic rebuttals (often by academic labs): sometimes they supposedly solve outstanding hard computational problems, sometimes their performances are dwarfed by classical machines. The goal of this article is to shed light on this back-and-forth, and explain what quantum computing could really be useful for.

Photoniques•Jan 1, 2025•0 citations

Quantum Artificial Intelligence for Natural Language Processing Applications

Ramin Ayanzadeh

Natural Language Processing and Semantic Web include several NP complete/hard problems that are intractable for classical computing machines. Even though distributed computing has provided remarkable advances (more precisely in dealing with big data), non-decomposable NP problems are still intractable in many real-world applications. And, from quantum computing perspective, solving complex problems with universal quantum gates requires developing of quantum algorithms. Considering commercializing quantum annealing machines by D-Wave, achieving global optimum for discrete optimization problems has been realized. In this study, a novel approach has been introduced to convert symbolic AI problems into quadratic unconstrained binary optimization (QUBO) form. More narrowly, this method represents classification of text documents (fragments) as optimizing a QUBO function. After embedding the train corpus into a QUBO function, D-Wave quantum annealer is used to classify new observations with finding the minimum energy level of the system.

ACM Technical Symposium on Computer Science Education (SIGCSE)•Feb 21, 2018•2 citations

Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization

Hartmut Neven, Geordie Rose, William G. Macready

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.

arXiv:0804.4457•Apr 28, 2008•55 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 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
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.
Quantum computing aims to outperform classical computers for some specific calculations. It relies on the additional resources given by the qubit superposition states, which can be used to design more efficiently. Reversibility of quantum computation may help in solving NP problems, which are easy in one direction but hard in the opposite sense. Quantum computers can enhance data processing and analysis tasks. The potential impact of quantum algorithms on optimization problems, simulation of quantum systems, and machine learning tasks such as clustering and classification. It also includes efforts to standardize quantum hardware and software interfaces, enabling interoperability and accelerating the adoption of quantum computing. The barriers we face while adopting Quantum computing are the accuracy of the information, lack of technical experts, and organizational interest in adopting the new process. We find one more critical barrier is the lack of standards of secure communication techniques while adopting quantum computing. While numerous challenges lie ahead, the promise of quantum computing in solving complex problems and driving innovation is too significant to ignore. We will examine the existing quantum algorithms and applications that have demonstrated quantum advantage or potential utility in various domains. The quantum computing field is expected to transition from physical qubits to error-corrected logical qubits. AI is likely to be unleashed by quantum computing for formidable progress advances in speed, cost, and algorithm learning function. Quantum computing solves one or two problems, with little practical use, and costs a fortune to run. Additionally, we will assess the challenges associated with scaling up quantum systems, addressing the issues of quantum coherence, error correction, and noise reduction.
Natural Language Processing and Semantic Web include several NP complete/hard problems that are intractable for classical computing machines. Even though distributed computing has provided remarkable advances (more precisely in dealing with big data), non-decomposable NP problems are still intractable in many real-world applications. And, from quantum computing perspective, solving complex problems with universal quantum gates requires developing of quantum algorithms. Considering commercializing quantum annealing machines by D-Wave, achieving global optimum for discrete optimization problems has been realized. In this study, a novel approach has been introduced to convert symbolic AI problems into quadratic unconstrained binary optimization (QUBO) form. More narrowly, this method represents classification of text documents (fragments) as optimizing a QUBO function. After embedding the train corpus into a QUBO function, D-Wave quantum annealer is used to classify new observations with finding the minimum energy level of the system.
Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.