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

Computing in Science & Engineering

Ask the hard questions

F. Sullivan

Published Oct 22, 2003• 0 citations
Publisher

Abstract

For particular classes of problems that we can state as generalizations of finding the period of a discrete function or locating an item on a discrete list, quantum computing promises a dramatic speedup over classical machines. Quantum computing has had a stimulating effect on the theory of computing, generated some excellent thinking about the foundations of quantum mechanics, and justified some elegant experimental work in applied physics. But, as was probably inevitable, it also has generated some myths. I think the myths actually affect public perception of what's possible in computing technology and, by implication, can lead to wild overestimates of what to expect from computational science.

DOI
10.1109/mcise.2003.1238695

Related papers

Quantum Computers: Myths and Reality

Andrei Yu. Khrennikov

Quantum computing is widely promoted as a transformative technology with the potential to revolutionize fields as diverse as artificial intelligence, finance, optimization, and materials science. Yet the public narrative surrounding quantum computing often diverges sharply from the technical realities acknowledged by specialists. This paper examines the roots of this discrepancy by distinguishing the genuine scientific achievements of quantum information theory from the speculative expectations projected onto quantum hardware. After outlining the central practical challenges posed by noise, decoherence, and the extreme overhead of quantum error correction, we argue that the path to large-scale, general-purpose quantum computers remains uncertain and potentially infeasible. Drawing a historical parallel with the nuclear fusion project, we illustrate how a theoretically elegant idea may confront fundamental obstacles in physical implementation. We further analyze the sources of technological hype in both scientific and popular discourse and highlight more realistic avenues for progress, such as quantum simulation and quantum-inspired classical computation. Finally, we revisit the conceptual foundations of quantum computational advantage and emphasize that constructive probability interference - rather than superposition or entanglement alone - may provide the true insight into quantum speedups. The goal of this note is not to diminish the value of quantum information research but to restore balance between promise and feasibility, clarifying what quantum computers can and cannot achieve in practice.

•Nov 28, 2025•0 citations

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 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 Algorithms in a Superposition of Spacetimes

Omri Shmueli

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question that arises is, what will physics allow in the future? Can more advanced theories of physics increase our computational power, beyond quantum computing? An active field of research in physics studies theoretical phenomena outside the scope of explainable quantum mechanics, that form when attempting to combine Quantum Mechanics (QM) with General Relativity (GR) into a unified theory of Quantum Gravity (QG). QG is known to present the possibility of a quantum superposition of causal structure and event orderings. In the literature of quantum information theory, this translates to a superposition of unitary evolution orders. In this work we show a first example of a natural computational model based on QG, that provides an exponential speedup over standard quantum computation (under standard hardness assumptions). We define a model and complexity measure for a quantum computer that has the ability to generate a superposition of unitary evolution orders, and show that such computer is able to solve in polynomial time two of the fundamental problems in computer science: The Graph Isomorphism Problem ($\mathsf{GI}$) and the Gap Closest Vector Problem ($\mathsf{GapCVP}$), with gap $O\left( n \sqrt{n} \right)$. These problems are believed by experts to be hard to solve for a regular quantum computer. Interestingly, our model does not seem overpowered, and we found no obvious way to solve entire complexity classes that are considered hard in computer science, like the classes $\mathbf{NP}$ and $\mathbf{SZK}$.

arXiv:2403.02937•Mar 5, 2024•0 citations

QUANTUM COMPUTING KNOWLEDGE PROVIDES AN EXPONENTIAL SPEEDUP TO HARD COMPUTATIONAL PROBLEMS: AN EXPERIENCE WITH ENGINEERING STUDENTS

Elvira Muñoz-García, Germán-Lenin Dugarte-Peña

QUANTUM COMPUTING KNOWLEDGE PROVIDES AN EXPONENTIAL SPEEDUP TO HARD COMPUTATIONAL PROBLEMS: AN EXPERIENCE WITH ENGINEERING STUDENTS

ICERI proceedings•Nov 1, 2022•0 citations

Item Listing Optimization for E-Commerce Websites Based on Diversity

Naoki Nishimura, Kotaro Tanahashi, Koji Suganuma +2 more

For e-commerce websites, deciding the manner in which items are listed on webpages is an important issue because it can dramatically affect item sales. One of the simplest strategies of listing items to improve the overall sales is to do so in a descending order of sales or sales numbers. However, in lists generated using this strategy, items with high similarity are often placed consecutively. In other words, the generated item list might be biased toward a specific preference. Therefore, this study employs penalties for items with high similarity being placed next to each other in the list and transforms the item listing problem to a quadratic assignment problem (QAP). The QAP is well-known as an NP-hard problem that cannot be solved in polynomial time. To solve the QAP, we employ quantum annealing (QA), which exploits the quantum tunneling effect to efficiently solve an optimization problem. In addition, we propose a problem decomposition method based on the structure of the item listing problem because the quantum annealer we use (i.e., D-Wave 2000Q) has a limited number of quantum bits. Our experimental results indicate that we can create an item list that considers both sales and diversity. In addition, we observe that using the problem decomposition method based on a problem structure can lead to a better solution with the quantum annealer in comparison with the existing problem decomposition method.

arXiv:1903.12478•Frontiers in Computer Science•Jul 16, 2019•60 citations
For particular classes of problems that we can state as generalizations of finding the period of a discrete function or locating an item on a discrete list, quantum computing promises a dramatic speedup over classical machines. Quantum computing has had a stimulating effect on the theory of computing, generated some excellent thinking about the foundations of quantum mechanics, and justified some elegant experimental work in applied physics. But, as was probably inevitable, it also has generated some myths. I think the myths actually affect public perception of what's possible in computing technology and, by implication, can lead to wild overestimates of what to expect from computational science.
Quantum computing is widely promoted as a transformative technology with the potential to revolutionize fields as diverse as artificial intelligence, finance, optimization, and materials science. Yet the public narrative surrounding quantum computing often diverges sharply from the technical realities acknowledged by specialists. This paper examines the roots of this discrepancy by distinguishing the genuine scientific achievements of quantum information theory from the speculative expectations projected onto quantum hardware. After outlining the central practical challenges posed by noise, decoherence, and the extreme overhead of quantum error correction, we argue that the path to large-scale, general-purpose quantum computers remains uncertain and potentially infeasible. Drawing a historical parallel with the nuclear fusion project, we illustrate how a theoretically elegant idea may confront fundamental obstacles in physical implementation. We further analyze the sources of technological hype in both scientific and popular discourse and highlight more realistic avenues for progress, such as quantum simulation and quantum-inspired classical computation. Finally, we revisit the conceptual foundations of quantum computational advantage and emphasize that constructive probability interference - rather than superposition or entanglement alone - may provide the true insight into quantum speedups. The goal of this note is not to diminish the value of quantum information research but to restore balance between promise and feasibility, clarifying what quantum computers can and cannot achieve in practice.
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 computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question that arises is, what will physics allow in the future? Can more advanced theories of physics increase our computational power, beyond quantum computing? An active field of research in physics studies theoretical phenomena outside the scope of explainable quantum mechanics, that form when attempting to combine Quantum Mechanics (QM) with General Relativity (GR) into a unified theory of Quantum Gravity (QG). QG is known to present the possibility of a quantum superposition of causal structure and event orderings. In the literature of quantum information theory, this translates to a superposition of unitary evolution orders. In this work we show a first example of a natural computational model based on QG, that provides an exponential speedup over standard quantum computation (under standard hardness assumptions). We define a model and complexity measure for a quantum computer that has the ability to generate a superposition of unitary evolution orders, and show that such computer is able to solve in polynomial time two of the fundamental problems in computer science: The Graph Isomorphism Problem (GI\mathsf{GI}GI) and the Gap Closest Vector Problem (GapCVP\mathsf{GapCVP}GapCVP), with gap O(nn)O\left( n \sqrt{n} \right)O(nn​). These problems are believed by experts to be hard to solve for a regular quantum computer. Interestingly, our model does not seem overpowered, and we found no obvious way to solve entire complexity classes that are considered hard in computer science, like the classes NP\mathbf{NP}NP and SZK\mathbf{SZK}SZK.
For e-commerce websites, deciding the manner in which items are listed on webpages is an important issue because it can dramatically affect item sales. One of the simplest strategies of listing items to improve the overall sales is to do so in a descending order of sales or sales numbers. However, in lists generated using this strategy, items with high similarity are often placed consecutively. In other words, the generated item list might be biased toward a specific preference. Therefore, this study employs penalties for items with high similarity being placed next to each other in the list and transforms the item listing problem to a quadratic assignment problem (QAP). The QAP is well-known as an NP-hard problem that cannot be solved in polynomial time. To solve the QAP, we employ quantum annealing (QA), which exploits the quantum tunneling effect to efficiently solve an optimization problem. In addition, we propose a problem decomposition method based on the structure of the item listing problem because the quantum annealer we use (i.e., D-Wave 2000Q) has a limited number of quantum bits. Our experimental results indicate that we can create an item list that considers both sales and diversity. In addition, we observe that using the problem decomposition method based on a problem structure can lead to a better solution with the quantum annealer in comparison with the existing problem decomposition method.