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