Quantum Computing by Practice: Python Programming in the Cloud with Qiskit and IBM-Q

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2024

V. SilvaQuantum Computing by Practice https://doi.org/10.1007/978-1-4842-9991-3_9

9. Quantum Advantage with Deutsch-Jozsa, Bernstein-Vazirani, and Simon’s Algorithms

Vladimir Silva¹  

(1)

CARY, NC, USA

 

In this chapter, we study three algorithms of little practical use but important because they were the first to show that quantum computers can solve problems significantly faster than classical ones. Consider the time complexities O(n) for the algorithms: classical vs. quantum in Table 9-1 (where n is the size of the input).

Table 9-1

Time complexities for Deutsch-Jozsa, Bernstein-Vazirani, and Simon algorithms

Name	Classical	Quantum
Deutsch-Jozsa	2n-1 ...