Abstract Alice and Bob introduce and explain in detail some of the algorithms that convinced physicists and computer scientists that there might be something to this crazy idea of quantum computing. Each algorithm provides a case study of how the properties of quantum states can be used to provide an advantage for using a quantum computer compared to a classical computer. Alice and Bob describe the Deutsch algorithm, designed to answer a simple question about the properties of functions of binary digits (0 and 1), and the Simon algorithm, which finds a “secret code.” The Simon algorithm, like many other quantum algorithms, is a mix of quantum state algorithms and classical computational methods. Alice and Bob also introduce Hadamard gates that act on multi-qubit systems. Those gates play an important role in many quantum algorithms.
Abstract Alice and Bob introduce and explain in detail some of the algorithms that convinced physicists and computer scientists that there might be something to this crazy idea of quantum computing. Each algorithm provides a case study of how the properties of quantum states can be used to provide an advantage for using a quantum computer compared to a classical computer. Alice and Bob describe the Deutsch algorithm, designed to answer a simple question about the properties of functions of binary digits (0 and 1), and the Simon algorithm, which finds a “secret code.” The Simon algorithm, like many other quantum algorithms, is a mix of quantum state algorithms and classical computational methods. Alice and Bob also introduce Hadamard gates that act on multi-qubit systems. Those gates play an important role in many quantum algorithms.
Although the basic ideas of quantum computation are fairly straightforward, the detailed manipulations required to extract a useful result from an entangled superposition of answers can be rather complicated. There are, however, a small number of algorithms which are simple enough to explain using only elementary methods. The best example is Deutsch's algorithm: as this only requires two qubits its properties are amenable to brute-force matrix calculations, and these calculations can be simplified using a variety of short cuts, which also give some insight into how and why the algorithm works. We will also explore the simplest case of Grover's quantum search algorithm, which is once again simple enough to be tacked by brute force. Finally we will look briefly at two methods used to stabilize quantum computers against errors. Deutsch's algorithm The invention of Deutsch's algorithm can be taken as defining the start of modern quantum computation, and it remains a key example, exhibiting many of the key properties of quantum algorithms in a particularly simple form. (Note, however, that the version of Deutsch's algorithm described here is not in fact the original but a later modification which is both more powerful and easier to understand.) Consider a binary function f from one bit to one bit, that is a function which takes in either 0 or 1 as its input and returns either 0 or 1 as its output. There are four such functions which may be conveniently labeled by their outputs as shown in Table 8.1.
Deutsch's algorithm and Grover's quantum search are theoretically interesting, but it is not obvious that these two algorithms are actually useful for anything important. We next consider a selection of more advanced algorithms, several of which may have real-life applications. Some of these will be too complicated to explain fully, and their properties will only be sketched briefly. The Deutsch–Jozsa algorithm Deutsch's algorithm is simple, but important, as it shows that a quantum algorithm can find a property of an unknown function (its parity) with a smaller number of queries than any possible classical algorithm (one rather than two). For this reason we can say that quantum computing is more efficient than classical computing within the oracle model of function evaluation. (It is widely believed that quantum computing is more efficient than classical computing in general, but this is a surprisingly hard thing to prove.) The simplicity of the algorithm is also an advantage, as it can be implemented on very primitive quantum computers. Beyond this, however, Deutsch's algorithm is also important as the simplest member of a large family of quantum algorithms, including most notably Shor's quantum factoring algorithm. The second simplest algorithm in the family is the Deutsch–Jozsa algorithm, which solves a very closely related problem. Consider an unknown binary function with n input bits, giving N = 2 n possible inputs, and a single output bit.
“An Introduction to Quantum Algorithms” provides an introduction to quantum algorithms, starting with the fundamentals of quantum computing. It covers the basics of quantum mechanics, the potential for quantum speedup, and the challenges and limitations of quantum computing. The chapter also highlights the key differences between classical and quantum computing, focusing on concepts such as bits and qubits, quantum measurement, superposition, and qubit properties, with a detailed explanation of qubit states on the Bloch sphere. Additionally, it explores quantum gates and algorithms, including single-qubit and multiple-qubit gates, the Quantum Fourier Transform (QFT), and important quantum algorithms such as Shor's algorithm for factoring, Grover's algorithm for searching, and Simon's algorithm for collision finding.
Abstract Alice and Bob explain the difference between classical (traditional) computing and quantum computing, deploying a gentle introduction to classical binary digits (bits) beginning with a brief history of the development of quantum mechanics and computer architecture. The abstract backbone of classical computing is logic gates, which represent changes to input bits under specific rules. These rules, governed by Boolean, logic can be summarized in truth tables, giving the output values for specific input values. The most common classical gates—NOT, AND, NAND, and XOR gates—are introduced. The vocabulary of classical computing provides the basis for understanding quantum computing.
Abstract Quantum Computing: From Alice to Bob provides a distinctive and accessible introduction to the rapidly growing fields of quantum information science (QIS) and quantum computing (QC). The book is designed for undergraduate students and upper-level secondary school students with little or no background in physics, computer science, or mathematics beyond secondary school algebra and trigonometry. While broadly accessible, the book provides a solid conceptual and formal understanding of quantum states and entanglement—the key ingredients in quantum computing. The authors give detailed treatments of many of the classic quantum algorithms that demonstrate how and when QC has an advantage over classical computers. The book provides a solid explanation of the physics of QC and QIS and then weds that knowledge to the mathematics of QC algorithms and how those algorithms deploy the principles of quantum physics to solve the problem. This book connects the physics concepts, the computer science vocabulary, and the mathematics, providing a complete picture of how QIS and QC work. The authors give multiple representations of the concept—textual, graphical, and symbolic (state vectors, matrices, and Dirac notation)—which are the lingua franca of QIS and QC. Those multiple representations allow the readers to develop a broader and deeper understanding of the fundamental concepts and their applications. In addition, the book provides examples of recent experimental demonstrations of quantum teleportation and the applications of quantum computational chemistry. The last chapter connects to the growing commercial world of QC and QIS and provides recommendations for further study.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.