程序代写代做代考 algorithm finance database COMP90038 – Algorithms and Complexity Lecture 23

COMP90038 – Algorithms and Complexity Lecture 23
COMP90038 Algorithms and Complexity
Lecture 23: Special Topics Quantum Computing
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274

COMP90038 – Algorithms and Complexity
Lecture 23
Review from Lecture 22: P vs NP
• The “P versus NP” problem comes from computational complexity theory.
• P means with polynomial time complexity
– That is, algorithms that have Ο poly( 𝑛)
– Sorting is a type of polynomial time problem
• NP means non-deterministic polynomial
– The answer can be checked in polynomial time, but cannot find the answer in polynomial time for large 𝑛.
– The TSP problem is an NP problem.
• This is the most important question in Computer Science

COMP90038 – Algorithms and Complexity
Lecture 23
Review from Lecture 22: NP-Completeness
• The main tool used to determine the class of a problem is reducibility.
• A decision problem 𝑃 is said to be polynomially reducible to a decision problem 𝑄,
if there exists a function 𝑡 that transforms instances of 𝑃 to instances of 𝑄 such that: – 𝑡 maps all yes instances of 𝑃 to yes instances of 𝑄 and all no instances of 𝑃 to
no instances of 𝑄
– 𝑡 is computable by a polynomial time algorithm.
• A decision problem 𝐷 is said to be NP-complete if: – it belongs to class NP
– Every problem in NP is polynomially reducible to 𝐷.

COMP90038 – Algorithms and Complexity
Lecture 23
NP-Complete Problems
• SAT, SUBSET-SUM, 3COL, LPATH and HAM, as well as thousands of other interesting and practically relevant problems have been shown to be NP-complete.
• This explains the continuing interest in NP-completeness and related concepts from complexity theory.
• For such problems, we do not know of solutions that are essentially better than exhaustive search.
• There are many other interesting complexity classes, including space complexity classes and probabilistic classes.

COMP90038 – Algorithms and Complexity
Lecture 23
Review from Lecture 22: Open Problems
• We do not know whether P=NP, and there are many other unsolved problems.
• We know that 𝑃 ⊆ 𝐸𝑋𝑃𝑇𝐼𝑀𝐸, that is, there are problems that can be solved in
exponential time but provably not in polynomial time.
• We also know:
𝑃 ⊆ 𝑅𝑃 ⊆ 𝑁𝑃 ⊆ 𝑃𝑆𝑃𝐴𝐶𝐸 ⊆ 𝑁𝑃𝑆𝑃𝐴𝐶𝐸 ⊆ 𝐸𝑋𝑃𝑇𝐼𝑀𝐸
• But which if these inclusions are strict? (Some must be; all could be…)

COMP90038 – Algorithms and Complexity
Lecture 23
Progress with the Travelling Salesman Problem
• There has been recent incremental improvement to finding approximate solutions to the traveling salesman problem: Computer Scientists Break Traveling Salesperson Record
• Computer scientists were able to improve on the best approximate solution from 1976 by 0.2 billionth of a trillionth of a trillionth of a percent.

COMP90038 – Algorithms and Complexity
Lecture 23
Quantum Computing Complexity
• The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP (“bounded error, quantum, polynomial time”).
• It is known that 𝐵𝑃𝑃 ⊆ 𝐵𝑄𝑃 (BPP=“bounded error, probabilistic, polynomial time”), and it is widely suspected that 𝐵𝑄𝑃⊈𝐵𝑃𝑃.
• The relationship of BQP to the basic classical complexity classes can be summarised as: P ⊆ 𝐵𝑃𝑃 ⊆ 𝐵𝑄𝑃 ⊆ 𝑃𝑃 ⊆ 𝑃𝑆𝑃𝐴𝐶𝐸, where PP = is a class of decision problems solvable by a “probabilistic Turing machine in polynomial time”.

COMP90038 – Algorithms and Complexity
Lecture 23
Motivation for Quantum Computing
• Inevitable?
– As transistor size < 10𝑛𝑚, the limit to classical mechanics is quickly approaching (atoms are about 1𝑛𝑚 or less). Moore’s Law “The number of transistors incorporated in a chip will approximately double every 24 months” — Gordon Moore, 1965 COMP90038 – Algorithms and Complexity Lecture 23 Motivation for Quantum Computing • More powerful? – Quantum computing algorithms have been proposed that solve certain computational problems faster than classical computers. COMP90038 – Algorithms and Complexity Lecture 23 Motivation for Quantum Computing • More powerful? – Quantum computing algorithms have been proposed that solve certain computational problems faster than classical computers. • There are broadly two classes of quantum computer. – Intermediate quantum computers (NISQ) • Medium-scale system (10 ∼ 1000 qubits) • Potentially polynomial speed-up • Optimisation, machine learning, chemistry, finance – Full universal quantum computers • Large-scale system (≫ 1000 qubits) • Potentially exponential speed-up (Shor’s) • Finance, bio-molecular simulation, database analysis COMP90038 – Algorithms and Complexity Lecture 23 Motivation for Quantum Computing • Cool? • Quantum computing could be used to simulate physical systems that the would be impossible on the largest supercomputers. – Condensed matter systems – Quantum Chemistry – Particle physics COMP90038 – Algorithms and Complexity Lecture 23 Quantum Computing Basics: Qubits • Quantum computers use quantum phenomenon such as superposition, entanglement and quantum measurement to perform computation. • Quantum superposition: systems can be in indeterminate (multiple) states prior to measurement. • Quantum entanglement: systems can be linked such that measurement of one part correlates to that of another part. • Quantum measurement: result of any given measurement a-priori unknown, system “collapses” to an outcome. Bits vs Qubits COMP90038 – Algorithms and Complexity Lecture 23 Quantum Computing Basics: Qubits • A bit can be either a 0 or a 1: OR • Qubits can be in superpositions: 𝜶𝟎+𝜷𝟏=𝜶 +𝜷 where:𝟎≔𝟏𝟎 and𝟏≔𝟎𝟏. • If we were to measure we would randomly obtain “0” with probability |𝜶|# or “1” with probability |𝜷|#. hZi |0i |i hYi hXi • Since probabilities must sum to 1: |1i |𝜶|# + |𝜷|# = 1 Bloch Sphere COMP90038 – Algorithms and Complexity Lecture 23 Exponential Scaling of Computational Space • 3 bits vs. 3 qubits 3 bits: 𝟎𝟏𝟎 3 qubits: 𝒂𝟎𝟎𝟎 +𝒃𝟎𝟎𝟏 +𝒄𝟎𝟏𝟎 +𝒅𝟎𝟏𝟏 +𝒆𝟏𝟎𝟎 +𝒇𝟏𝟎𝟏 +𝒈𝟏𝟏𝟎 +𝒉𝟏𝟏𝟎 300 bits vs. 300 qubits 300 bits: 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 𝟎𝟏𝟎𝟎𝟏𝟎𝟏𝟎𝟎𝟎 • 300 qubits: ? 2$%%~10&% dimensional state space! Total number of atoms in the universe ~10'(. COMP90038 – Algorithms and Complexity Lecture 23 Quantum Computing Basics: Entanglement • Entanglement is a special property of the quantum world with no classical analogue. Independent 𝟎𝟎 ) 𝟏𝟏 = * ## Entangled 50% 0% 0% 50% 25% 25% 25% 25% + • • Even after more than 100 years of research, we still don’t fully understand entanglement. Entanglement enables – Teleportation: transfer of quantum information – Dense coding: encoding two classical bit of information per qubit COMP90038 – Algorithms and Complexity Lecture 23 Gates on Bits Vs. Operations on Qubits • Quantum Gates = Operations – X, Z, CNOT, H, Toffoli, ... – Acts in qubit(s): can change amplitude and/or phase [complex numbers]. • Logical Gates – AND, OR, NOT, XOR, NAND, ... – Acts on bit(s). – Final output is a well-defined bit (single digit). – Final output can be a superposition state and measurement is done to determine the value. COMP90038 – Algorithms and Complexity Lecture 23 Circuit Model Classical Digital Circuit Quantum Circuit Two input gate input Single input gate Complex numbers Superposition Probabilistic amplitudes Entanglement Measurement Time steps COMP90038 – Algorithms and Complexity Lecture 23 Example 1: Deutsch-Jozsa Algorithm • One of the first quantum algorithms proposed (1992) that showed a quantum advantage over classical computing. • No well-defined real-world application. • Inspiration for the inspiration for Shor’s famous algorithm. • Problem statement: Given a Boolean function, 𝑓(𝑥), determine if: 𝑓(𝑥) is constant (always gives the same result), or 𝑓(𝑥) is balanced (gives equal numbers of 0’s and 1’s). COMP90038 – Algorithms and Complexity Lecture 23 Example 1: Deutsch-Jozsa Algorithm • Examples: for an input “𝑥” of “𝑛” bits, the function 𝑓 𝑥 is: • Elementary operation: evaluation of 𝑓 𝑥 for 𝑥 [depends on 𝑛]. • Classical algorithm (worst case) needs (2!/2)+1 queries Time complexity = Ο(2!) • Quantum algorithm needs just 1 query Time complexity = Ο(1). COMP90038 – Algorithms and Complexity Lecture 23 Example 1: Deutsch-Jozsa Algorithm • For the one qubit input case, the implementations for 4 choices of function are: 𝟎 𝟎 𝑋 ! 1000 00→00 = 0 1 0 0 01 → 01 0001 10→11 0010 11→10 ! 𝟎 ! 𝟎 𝑋 COMP90038 – Algorithms and Complexity Lecture 23 Example 1: Deutsch-Jozsa Algorithm 𝟎 𝟏 𝐻 𝐻 = 1 2 11 1 −1 𝐻 𝑈" 𝐻 0→1 0+1 2 1→1 0−1 2 The Deutsch-Jozsa algorithm determines in just one query whether the function is constant or balanced. Classically, this would require two queries. COMP90038 – Algorithms and Complexity Lecture 23 Example 1: Deutsch-Jozsa Algorithm 𝐻 𝟎 𝟏 𝐻 𝐻 𝑈" 𝐻 𝐻 This multi-qubit Deutsch-Jozsa algorithm will still require only one query to determine whether the function is constant or balanced. Note: 0’s in the output register → constant, any other value → balanced. 𝟎 ↓ 𝟎 𝟎 𝟎 ⋮ 𝟎 𝐻 𝐻 𝐻 COMP90038 – Algorithms and Complexity Lecture 23 Example 2: Grover’s Search Algorithm • One of the first (1996) quantum algorithms to show a speed-up compared to it’s classical counterpart for a useful problem. • Based on amplitude amplification, something that is uniquely available to quantum systems. Has formed the basis for many future quantum algorithms. • Problem: An unsorted list of 𝑁 entries could be searched to find a marked item with Ο 𝑁 steps instead of the best classical result of Ο 𝑁 . COMP90038 – Algorithms and Complexity Lecture 23 Example 3: Shor’s Factoring algorthm • The first (1994) quantum algorithms to show an exponential speed-up compared to it’s classical counterpart. • Is a generalisation of the quantum phase estimation algorithm: 𝑈 𝜙 =𝑒!"# 𝜙 , 0 ≤ 𝜃 < 1 • Problem: given an integer 𝑁 as an input find the integers 1 < 𝑁*, 𝑁# < 𝑁 such that 𝑁 = 𝑁*𝑁#. • Key part of the algorithm is to find the order of 𝑥 𝑚𝑜𝑑 𝑁: find 𝑟 such that 𝑥+ = 1 𝑚𝑜𝑑 𝑁 . • Classically the running time is: Ο 𝑒𝑥𝑝 $ ,- 𝑛 (log 𝑛)# , where 𝑛 = log 𝑁 & • Quantum runs in Ο 𝑛$ log 𝑛 and uses Ο 𝑛# log 𝑛 log log 𝑛 gates. COMP90038 – Algorithms and Complexity Lecture 23 Example 4: Solve Linear Systems of Equations • Solving linear systems is central to a majority of science, engineering, finance and economics applications. • Problem: given a system 𝐴𝑥⃗ = 𝑏, find 𝑥⃗. • Equivalent to: 𝐴 𝑥 = 𝑏 with solution 𝑥 = .%& / . ||.%& / || • Provided the linear systems is sparse and has a low condition number 𝜅, the quantum algorithm has a runtime of Ο log(𝑁) 𝜅# . • Classically, the fastest algorithm runs in Ο 𝑁𝜅 , an exponential speedup. COMP90038 – Algorithms and Complexity Lecture 23 Example 5: Linear Algebra • Many linear algebra techniques can be performed exponentially faster on a quantum computer. • Assume 𝑁 = 21, so 𝑛 = log 𝑁. Technique Classically Quantum FFT Ο N log(𝑁) Ο (log(𝑁))# Eigenvectors/eigenvalues Ο𝑁$ toΟ𝑁# Ο (log(𝑁))# Matrix inversion Ο 𝑁$ toΟ Nlog(𝑁) Ο (log(𝑁))$ • These are the basic operations required for most machine learning protocols. COMP90038 – Algorithms and Complexity Lecture 23 Example 6: Quantum Supremacy • Google recently achieved quantum computational supremacy with a 53-qubit superconducting device. • Circuit depths up to 20 layers. • Classical simulations predicted to take 10,000 years. • Quantum solution takes about 200 seconds. COMP90038 – Algorithms and Complexity Lecture 23 Emerging Quantum Computing Industry • Companies building the hardware are using six main physical systems: Silicon COMP90038 – Algorithms and Complexity Lecture 23 Emerging Quantum Computing Industry • There are now a lot of quantum computing companies. COMP90038 – Algorithms and Complexity Lecture 23 Coming Up Next • Review Lecture