Quantum Computing: Lecture Notes
arXiv:1907.09415
Abstract
This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science. The first version was written in 2011, with many extensions and improvements in subsequent years. The first 10 chapters cover the circuit model and the main quantum algorithms (Deutsch-Jozsa, Simon, Shor, Hidden Subgroup Problem, Grover, quantum walks, Hamiltonian simulation and HHL). They are followed by 4 chapters about complexity, 4 chapters about distributed ("Alice and Bob") settings, a chapter about quantum machine learning, one about stabilizer states and Clifford circuits, and a final chapter about quantum error correction. Appendices A and B give a brief introduction to the required linear algebra and some other mathematical and computer science background. All chapters come with exercises, with some hints provided in Appendix C.
arXiv commentVersion 6: added a new chapter about stabilizer states and Clifford circuits, more exercises, and many small improvements of the text throughout
References in corpus (30)
- Quantum algorithm for solving linear systems of equations
- Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
- Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
- Strengths and Weaknesses of Quantum Computing
- Quantum Error Correction for Quantum Memories
- Quantum Algorithms Revisited
- Quantum fingerprinting
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Non-locality and Communication Complexity
- Substituting Quantum Entanglement for Communication
- Hamiltonian simulation with nearly optimal dependence on all parameters
- A Quantum Algorithm for Finding the Minimum
- An approximate Fourier transform useful in quantum factoring
- Search via Quantum Walk
- Graph Isomorphism in Quasipolynomial Time
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- The cost of exactly simulating quantum entanglement with classical communication
- Negative weights make adversaries stronger
- Quantum communication complexity of symmetric predicates
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Complexity limitations on quantum computation
- Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer
- The quantum query complexity of the hidden subgroup problem is polynomial
- Threshold Accuracy for Quantum Computation
- Classical computing, quantum computing, and Shor's factoring algorithm
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Lower Bounds on Quantum Query Complexity
- PSPACE has 2-round quantum interactive proof systems
Cited by in corpus (11)
- Unleashing the power of disruptive and emerging technologies amid COVID-19: A detailed review
- Computationally Efficient Quantum Expectation with Extended Bell Measurements
- Quantum Distributed Complexity of Set Disjointness on a Line
- Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs
- Near-Optimal Quantum Algorithms for String Problems
- Unitary Subgroup Testing
- An Economic Model for Quantum Key-Recovery Attacks against Ideal Ciphers
- On quantum preimage attacks
- Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
- Sublinear quantum algorithms for estimating von Neumann entropy
- Global Optimum Search in Quantum Deep Learning