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

International Symposium on Applied Sciences in Biomedical and Communication Technologies

Complexity considerations quantum computation

Luigi Accardi

Published Nov 1, 2010• 2 citations
Publisher

Abstract

It is usually claimed that quantum computer can outperform classical computer. Is this statement true? We discuss this issue, not in general, but in the context of the most famous algorithm of quantum computation: Shor's algorithm.
DOI
10.1109/isabel.2010.5702891

Related papers

COMPLEXITY CONSIDERATIONS QUANTUM COMPUTATION

Luigi Accardi

It is usually calimed that quantum computer can outperform classical computer.Is this statement true?We discuss this issue, not in general, but in the context of the most famous algorithm of quantum computation: Shor's algorithm.

QP-PQ, quantum probability and white noise analysis•Mar 1, 2013•0 citations

Complexity and algorithms in quantum computation

Richard Jozsa

In 1982 Feynman noted that the simulation of a quantum process on a classical computer appears to generally involve an exponential slowdown in running time compared to the evolution of the process itself. More recently in quantum computation this effect has been turned around and exploited for computational advantage by formulating quantum processes (quantum algorithms) whose evolution corresponds to the performance of useful computational tasks. Thus the quantum algorithm will engender an exponential speedup in computing time. The most famous such quantum algorithm is Shor's algorithm for factorising whole numbers. It factorises a number having d digits in a time of order less than d whereas no known classical algorithm can perform factorisation in a time bounded by any polynomial in d. In theoretical computer science, computational complexity is generally characterised by classifying computational tasks into complexity classes such as P, BPP and NP. It therefore appears that quantum computers will be able to transgress some of the boundaries set by these classes. (2 pages)

•Jan 1, 1997•15 citations

Lower Bounds on Quantum Query Complexity

Peter Høyer, Robert Špalek

Shor's and Grover's famous quantum algorithms for factoring and searching show that quantum computers can solve certain computational problems significantly faster than any classical computer. We discuss here what quantum computers_cannot_ do, and specifically how to prove limits on their computational power. We cover the main known techniques for proving lower bounds, and exemplify and compare the methods.

arXiv:quant-ph/0509153•Sep 21, 2005•51 citations

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•103 citations

Shor's algorithm and Grover's algorithm in quantum computing.

Chris Valle

In this paper we will analyse two quantum algorithms that sparked interest in the potential of quantum computers. The first is Lov Grover's algorithm which may be used to conduct a type of database search. The second is Peter Shor's algorithm which may be used to factor large numbers and provides an exponential speed up over the best current classical algorithms. In the context of these two algorithms we will discuss the benefits and weaknesses of quantum computation. We will show that in exchange for a quantum computer's greater speed we must accept an inherent level of uncertainty in our results.

•Jan 1, 2011•1 citation

Effectiveness of quantum algorithms on classical computing complexities

Hicham Amellal, Abdelmajid Meslouhi, Abderrahim El Allati

In this paper, we analyze the effectiveness of quantum algorithms to solve some classical computing complexities. In fact, we focus in this study on several famous quantum algorithms, where we discussed their impact on classical computing using in computer science.

International Conference on Smart City Applications (SCA)•Oct 10, 2018•2 citations
In 1982 Feynman noted that the simulation of a quantum process on a classical computer appears to generally involve an exponential slowdown in running time compared to the evolution of the process itself. More recently in quantum computation this effect has been turned around and exploited for computational advantage by formulating quantum processes (quantum algorithms) whose evolution corresponds to the performance of useful computational tasks. Thus the quantum algorithm will engender an exponential speedup in computing time. The most famous such quantum algorithm is Shor's algorithm for factorising whole numbers. It factorises a number having d digits in a time of order less than d whereas no known classical algorithm can perform factorisation in a time bounded by any polynomial in d. In theoretical computer science, computational complexity is generally characterised by classifying computational tasks into complexity classes such as P, BPP and NP. It therefore appears that quantum computers will be able to transgress some of the boundaries set by these classes. (2 pages)
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
In this paper we will analyse two quantum algorithms that sparked interest in the potential of quantum computers. The first is Lov Grover's algorithm which may be used to conduct a type of database search. The second is Peter Shor's algorithm which may be used to factor large numbers and provides an exponential speed up over the best current classical algorithms. In the context of these two algorithms we will discuss the benefits and weaknesses of quantum computation. We will show that in exchange for a quantum computer's greater speed we must accept an inherent level of uncertainty in our results.