Classical and Quantum Computing

by Hardy, Yorick; Steeb, Willi-Hans

• ISBN13: 9783764366100
• ISBN10: 3764366109
• Format: Paperback
• Copyright: 2002-01-01
• Publisher: Birkhauser

Summary

"Classical and Quantum computing" provides a self-contained, systematic and comprehensive introduction to all the subjects and techniques important in scientific computing. The style and presentation are readily accessible to undergraduates and graduates. A large number of examples, accompanied by complete C++ and Java code wherever possible, cover every topic. Features and benefits:- Comprehensive coverage of the theory with many examples- Topics in classical computing include boolean algebra, gates, circuits, latches, error detection and correction, neural networks, Turing machines, cryptography, genetic algorithms - For the first time, genetic expression programming is presented in a textbook- Topics in quantum computing include mathematical foundations, quantum algorithms, quantum information theory, hardware used in quantum computingThis book serves as a textbook for courses in scientific computing and is also very suitable for self-study. Students, professionals and practitioners in computer science, applied mathematics and physics will benefit from using the book and the included software simulations.

Table of Contents

List of Tables	xiii
List of Figures	xv
List of Symbols	xix
Preface	xxi
I Classical Computing
Algorithms
Algorithms	3	(3)
Algorithm Verification	6	(4)
Random Algorithms	10	(5)
Total and Partial Functions	15	(3)
Alphabets and Words	18	(5)
Boolean Algebra
Introduction	23	(1)
Definitions	24	(2)
Rules and Laws of Boolean Algebra	26	(1)
DeMorgan's Theorem	27	(1)
Further Definitions	27	(5)
Boolean Function Implementation	32	(9)
Karnaugh Maps	35	(3)
Quine-McKluskey Method	38	(3)
Example Programs	41	(10)
Efficient Set Operations Using Boolean Algebra	41	(5)
Quine-McKluskey Implementation	46	(5)
Number Representation
Binary, Decimal and Hexadecimal Numbers	51	(21)
Conversion	53	(5)
Arithmetic	58	(2)
Signed Integers	60	(7)
Overflow	67	(3)
Binary-Coded Decimal Form	70	(2)
Floating Point Representation	72	(7)
Introduction	72	(2)
Representation	74	(5)
Logic Gates
Introduction	79	(1)
Gates	80	(7)
AND Gate	80	(1)
OR Gate	81	(1)
XOR Gate	82	(1)
NOT Gate (Inverter)	83	(1)
NAND Gate	84	(1)
NOR Gate	85	(1)
XNOR Gate	86	(1)
Buffer	87	(1)
Tri-State Logic	88	(1)
Feedback and Gates	89	(2)
Combinational Circuits
Introduction	91	(1)
Decoder	92	(1)
Encoder	93	(3)
Demultiplexer	96	(1)
Multiplexer	97	(1)
Binary Adder	98	(4)
Binary Half Adder	98	(1)
Binary Full Adder	99	(1)
Binary Four-Bit Adder	100	(1)
Faster Addition	101	(1)
Binary Subtraction	102	(1)
Binary Multiplication	103	(4)
Unsigned Integer Multiplication	103	(2)
Fast Multiplication	105	(1)
Signed Integer Multiplication	106	(1)
Binary Division	107	(1)
Magnitude Comparator	108	(2)
4-Bit ALU	110	(2)
Read Only Memory (ROM)	112	(1)
Combinational Programmable Logic Devices	113	(4)
Programmable Gate Arrays	117	(1)
VHDL	118	(1)
Latches and Registers
Introduction	119	(1)
SR Latch	120	(1)
D Latch	121	(1)
JK Latch	122	(1)
D Register	123	(1)
JK Register	124	(1)
Synchronous Circuits
Introduction	125	(2)
Shift Registers	127	(2)
Binary Counter	129	(4)
Example Program	133	(2)
Recursion
Introduction	135	(5)
Example Programs	140	(12)
Mutual Recursion	152	(4)
Wavelets and Recursion	156	(6)
Primitive Recursive Functions	162	(3)
Backtracking	165	(3)
Stacks and Recursion Mechanisms	168	(3)
Recursion Using Stacks	168	(1)
Stack Free Recursion	169	(2)
Abstract Data Types
Introduction	171	(1)
Linked List	172	(15)
Stack	187	(3)
Tree	190	(7)
Error Detection and Correction
Introduction	197	(1)
Parity Function	198	(1)
Hamming Codes	199	(5)
Weighted Checksum	204	(1)
Noiseless Coding Theorem	205	(3)
Example Programs	208	(7)
Cryptography
Introduction	215	(1)
Classical Cypher Systems	216	(5)
Public Key Cryptography	221	(8)
Finite State Machines
Introduction	229	(1)
Finite Automata	230	(3)
Finite Automata with Output	233	(5)
Turing Machines	238	(6)
Example Programs	244	(7)
Computability and Complexity
Introduction	251	(1)
Computability	252	(2)
Church's Thesis	252	(1)
The Halting Problem	253	(1)
Godel's Incompleteness Theorem	254	(2)
Godel Numbering	254	(2)
Godel's Incompleteness Theorem	256	(1)
Complexity	256	(5)
Complexity of Bit Strings	256	(3)
NP-class of Problems	259	(2)
Neural Networks
Introduction	261	(5)
Hyperplanes	266	(2)
Perceptron	268	(26)
Introduction	268	(4)
Boolean Functions	272	(3)
Perceptron Learning	275	(4)
Quadratic Threshold Gates	279	(3)
One and Two Layered Networks	282	(1)
Perceptron Learning Algorithm	283	(6)
The XOR Problem and Two-Layered Networks	289	(5)
Multilayer Perceptrons	294	(19)
Introduction	294	(1)
Cybenko's Theorem	295	(1)
Back-Propagation Algorithm	296	(17)
Genetic Algorithms
Introduction	313	(2)
The Sequential Genetic Algorithm	315	(5)
Gray Code	320	(3)
Schemata Theorem	323	(3)
Markov Chain Analysis	326	(2)
Bit Set Classes in C++ and Java	328	(5)
A Bit Vector Class	333	(4)
Maximum of One-Dimensional Maps	337	(9)
Maximum of Two-Dimensional Maps	346	(10)
The Four Colour Problem	356	(4)
Problems with Constraints	360	(20)
Introduction	360	(2)
Knapsack Problem	362	(6)
Traveling Salesman Problem	368	(12)
Other Applications for Genetic Algorithms	380	(1)
Distributed Global Optimization	381	(3)
Genetic Programming	384	(8)
Gene Expression Programming	392	(11)
II Quantum Computing
Quantum Mechanics
Hilbert Spaces	403	(14)
Linear Operators in Hilbert Spaces	417	(14)
Schmidt Decomposition	431	(3)
Spin Matrices and Kronecker Product	434	(8)
Postulates of Quantum Mechanics	442	(9)
Quantum Bits and Quantum Computation
Introduction	451	(1)
Quantum Bits and Quantum Registers	452	(3)
Quantum Bits	452	(1)
Quantum Registers	453	(2)
Entangled States	455	(8)
Quantum Gates	463	(13)
Introduction	463	(1)
NOT Gate	464	(1)
Walsh-Hadamard Gate	465	(2)
XOR and the Controlled NOT Gate	467	(1)
Other Quantum Gates	468	(3)
Universal Sets of Quantum Gates	471	(1)
Functions	472	(4)
Garbage Disposal	476	(1)
Quantum Copying	477	(3)
Example Programs	480	(11)
Measurement and Quantum States
Introduction	491	(1)
Measurement Problem	492	(1)
Copenhagen Interpretation	493	(2)
Hidden Variable Theories	495	(1)
Everett Interpretation	496	(2)
Basis Degeneracy Problem	498	(2)
Information Theoretic Viewpoint	500	(1)
Quantum State Machines
Introduction	501	(1)
Quantum Automata	501	(3)
Quantum Turing Machines	504	(3)
Teleportation
Introduction	507	(1)
Teleportation Algorithm	508	(3)
Example Program	511	(4)
Quantum Algorithms
Deutsch's Problem	515	(4)
Simon's Problem	519	(3)
Quantum Fourier Transform	522	(2)
Factoring (Shor's Algorithm)	524	(4)
The Hidden Subgroup Problem	528	(2)
Unstructured Search (Grover's Algorithm)	530	(7)
Quantum Key Distribution	537	(2)
Dense Coding	539	(2)
Quantum Information Theory
Introduction	541	(1)
Von Neumann Entropy	542	(1)
Measures of Entanglement	543	(5)
Bell's Inequality	543	(2)
Entanglement of Formation	545	(1)
Conditions on Entanglement Measures	546	(2)
Quantum Coding	548	(6)
Holevo Bound	554	(1)
Quantum Error Detection and Correction
Introduction	555	(1)
The Nine-qubit Code	556	(2)
The Seven-qubit Code	558	(1)
Efficiency and the Five-qubit Code	559	(2)
Stabilizer Codes	561	(2)
Quantum Hardware
Introduction	563	(1)
Trapped Ions	564	(1)
Cavity Quantum Electrodynamics	565	(1)
Quantum Dots	566	(3)
Nuclear Magnetic Resonance Spectroscopy	569	(2)
Internet Resources	571	(2)
Bibliography	573	(12)
Index	585