CS880 - Quantum Computing

# CS880 - Quantum Computing * Quantum Computer do things classic computer cannot Complexity Theory * How Power of Quantum Computer outnumber Classic Computer. Involves running time, memory usage * Show probablistic results (Main focus of this course) * Show some impossibility result ## Brief History of Quantum Algorithms Main focus is on algorithms. * ALgorithm transform input to a valid output. * Also develops into other computation we may want to do * History line * 80' * Simulating quantum system is hard on classic computers. * Quantum Computer may also help solve problems in the classic field. * Important contribution at the era: Formalization of the model. (Variation of Classic Turing Machine) * People start to come up with toy problem where quantum performance is provably better than its classic counterpart * Polynomial improvements (In Nowadays, quantum advantage) * Exponential Improvements (Nowadays, formalized as quantum supremacy) Problems unsolvable becomes solvable in the quantum realm * 90's Grover's Algorithm: Find an element in an unsorted database using only $O(\sqrt{n})$ queries. (The notion of a query is different in the quantum definition. Also, this does not count in the time to set up the database, or equivalently, the quantum circuit, which may require even more than linear time complexity). Can use Grover's Algorithm to solve boolean satisfiability problem. Classically, could only exhaustively search the entire space. (Exponential time hypothesis: cannot actually do better than that). With Grover's algorithm can get $O(\sqrt(2^n))$ algorithm for quantum computer. The main technique used is called amplitude amplification. Applied to other problem that has the flavor of investigating certain aspects of a database. An alternative way of obtaining it the "quantum walk": which is the quantum equivalence of "random walk". The elementary quantum operations involved in the algorithm is simple. * Shor's Algorithm: An $O(\sqrt{n^2})$ for factoring integers. Classically, it is $2^{O(n^{\frac{1}{3}})}$. It is important because it forms the basis of public encryption system. (RSA) Private key is needed to decode the message sent. In principle, public key contains all information about the private key, but the decoding process is presumably hard. If we are able to factor the public key (a product of two primes), private keys are just a factorization of the public key. Both theorists and practitioners (even federal agents) get interested in the topic. The technique used it Fourier sampling (eigenvalue estimations). The technique is also employed at several other problems. * Discrete Log Problem (Another number theory problem which forms the basis of crypto system). * Hidden subgroup problem. Goal is to figure out a subgroup in a larger group while given a function that is constant over the [cosets](https://en.wikipedia.org/wiki/Coset). * Solving systems of linear equations. Classically can be solved in order of $O(n^3)$. But with eigenvalue decomposition, could do it in $O(poly(\log N))$. The system needs to be well-conditioned and also needs to be provided in the right way. * Clustering Problem. Provide an exponential speed-up compared to the classic algorithm at the time (2017). Afterwards, an undergraduate students come up with a classic algorithm which attains the same running time improvement. * Challenges * Graph isomorphism problem. Given two graphs, if they are convertible by relating vertices. Can cast as a Hidden subgroup problem. But becomes less interesting in the quantum community as two years ago, a more efficient algorithms for the problem proposed that achieve $O(n^{\log n})$. * Lattice problem: In n-d space, want to find a lattice that is closed to points. Also used in crypto system, alternative to prime numbers. Still not vulnerable to quantum systems. * In general, it seems quantum improvement often happens in NP-intermediate area. * The best prime number factoring is (15,21) as it becomes harder to maintain error control. (The operation used in SHOR's algorithm is much harder). In Quantum computing, we are no longer working with binary entity but reals. It is additional challenge to design error correction code. Also, error-correction operations produces extra errors. * '10 Sampling Problems. Generate samples from a certain distributions. Becomes easier to establish quantum supremacy as it is a larger class of problems. For sampling problems, there are more techniques for us to show classic problems cannot do well in somewhat simpler problems. * Boson Sampling. Very simple quantum operations but classically, we can conditionally (polynomial hierachy does not collapse) show that. Besides, approximate sampling is still not possible in classic. * Announcement from Google this year: Outputs of a random quantum algorithm. Pick quantum circuit from random. These circuits are not easy to simulate classically. Roughly 60 qubits are enough to do the simulation. * Other information processing task * Communication: Two parties want to jointly solve a task when each knows part of information required. Want to get the least amount of communication. Provably, exponential improvements are obtained. * Private key generation: Two parties want to communicate. They must first agree on a common key. In the quantum realm, the parties can set up a channel without getting together physically. For high confidence, they can make sure they will get common key and if a third party has intercepted the key, the activity can be detected. Recent development: no longer requires quantum computers are reliable. * Interaction between classic and quantum system. * Verification: whether other has performed computation to achieve the answer. * Zero-knowledge system: authentication systems. Convince someone we have a certain piece of knowledge without revealing it. Much safer than classic system like password. By running the authentication protocol, an observer won't learn anything than the user indeed has access to the necessary priviledge. In the quantum setting, we still want to verify a classic system is still safe from third party observer even if they have access to quantum power. ## Physical Realizations Quantum effects only on either microscopic level or environment of extreme conditions. - Microscopic approach: qubits are realized by a single microscopic entity: ion, atom (research on campus is working on neutral atom), electron, photon. Atoms are kept in laser light for stability. To realize operations, use neighboring atoms to interact with the computer atom (for example, AND operation). The bottle-neck is the size of the system. The laser used puts restriction on the magnitude of the systems (Around 100~200 qubits). Another approach on campus is to use electrons. (in semi-conductors material) It is more challenging to get neighboring electrons to interact with each other to realize logic gate operations. Once that works, we can use the known silicon technology to scale up the system to a much larger size. - Macroscopic Systems: Need the environment temperature to be closed to be absolute 0. (After removed from lab, take half of a year to recover the experiment condition). Use super-conducting circuits. When condition is reached, Quantum behavior for an aggregation of entities. So far, the most promising approach. ## Outline 0. Formal Model. 1. Quantum Algorithm paradigms (Quantum walks, Fourier Sampling, Eigenvalue estimation) 2. Other information processing tasks 3. Error Correction and fault tolerance ## Logistics Prerequisite: Linear Algebra, Probability, Algorithms Text has appendix - Go over the appendix Appendix: B1 (Basic Maths) B2 (Basic Probability and Algorithms) A (1-8) (Linear Algebra) More advanced stuff Homework: 1. Scribe some of the lectures. 2. Small problems to test 3. Alternatives: Projects / Free HW assignments Office Hour: Tuesday 1-2pm > Topics will heavily rely on linear algebra and probability theory.