MULT90063 Introduction to Quantum Computing
Lecture 23
Quantum Computing architectures and quantum complexity classes
Lecture 24
Copyright By PowCoder代写 加微信 powcoder
Quantum Computing Review
HHL algorithm using the QUI
MULT90063 Introduction to Quantum Computing
Quantum Computing Review Lecture 24
MULT90063 Introduction to Quantum Computing
Review (Selected Highlights)
MULT90063 Introduction to Quantum Computing
Linear Algebra and Dirac notation
| i=a|0i+b|1i
For qubits we can use column vectors to represent a convenient basis for kets:
|0i= 10 |1i = 0
Computational basis states
a|0i+b|1i= a b
General qubit state a, b are “amplitudes”
MULT90063 Introduction to Quantum Computing
The Bloch Sphere
A convenient geometric representation of single qubit states is the Bloch sphere:
|0i |1i hYi
|0i i|1i
|0i + |1i p2
|0i + i|1i
MULT90063 Introduction to Quantum Computing
Single Qubit Gates
Circuit symbol:
Matrix representation:
Action on ket states:
↵|0i + |1i ! ↵|1i + |0i i Im
QUI example:p
3 |0i + i |1i
complex amplitudes
↵|0|0ii+ |1|1ii!↵↵|1|i1i++ |0|i0i
↵↵|0|0ii++ |1|i1i!!↵↵|1|i1+i + | 0
MULT90063 Introduction to Quantum Computing
Multiple Qubit States
26ac37 a ⌦ c =64ad75
00 amplitude 01 amplitude 10 amplitude 11 amplitude
| i=a|0i+b|1i | i=c|0i+d|1i
MULT90063 Introduction to Quantum Computing
Two qubit operations
↵|0i+ |1i |0i
|i |0i Before the CNOT, the state is:
| i=(↵|0i+ |1i)⌦|0i=↵|00i+ |10i
After the CNOT, the state is:
| 0i=↵|00i+ |11i
MULT90063 Introduction to Quantum Computing
Using the QUI
In labs you will learn to use the “Quantum User Interface” (QUI) to construct circuits. Your first lab will be all about single qubit rotations.
MULT90063 Introduction to Quantum Computing
Entanglement
We can never find a, b, c, d, s.t.
|00i + |11i
p2 6= (a |0i + b |1i) ⌦ (c |0i + d |1i)
A state which is not separable is called an entangled state.
Entanglement is a uniquely quantum mechanical property, with no direct classical analogue.
MULT90063 Introduction to Quantum Computing
Dense Coding Circuit
|0i + |1i |00i ! p2 |0i
|00i + |11i ! p2
|00i + |11i |00i + |11i p2 ! p2
|00i + |11i |01i + |10i p2 ! p2
|00i + |11i |00i |11i
0,1 Z2 p2 ! p2
|00i + |11i |01i |10i 1,1 X2Z2 p2 ! p2
Bell state preparation:
Bell state preparation
Alice encoding
Bob’s measurement
Alice applies one of four different operations to her qubit, based on the classical information she would like to send.
MULT90063 Introduction to Quantum Computing
Teleportation
↵ |0i + |1i
Alice measures
0, 0 0, 1 1, 0 1, 1
↵ |0i + |1i
i.e. after correction Bob has successfully reconstructed
Alice’s original state.
↵|0i + |1i ! ↵|0i + |1i X(↵|1i + |0i) ! ↵|0i + |1i Z(↵|0i |1i) ! ↵|0i + |1i ZX(↵|1i |0i) ! ↵|0i + |1i
Bob’s qubit
↵|0i + |1i ↵|1i + |0i ↵|0i |1i ↵|1i |0i
MULT90063 Introduction to Quantum Computing
Deutsch-Josza algorithm
• Given a boolean function, f, determine if:
f is constant (always gives the same result), or
f is balanced (gives equal numbers of 0s and 1s)
• Classical algorithm (worst case) needs 2n/2+1 queries
• Quantum algorithm needs just 1 query.
MULT90063 Introduction to Quantum Computing
Bernstein-Vazirani Algorithm
Given a Boolean function, f:
f(x)=x·s mod2 find s.
x · s = X xisi i
• Classical algorithm needs n queries
• Quantum algorithm needs just 1 query.
MULT90063 Introduction to Quantum Computing
Simon’s Algorithm
Given a 2-to-1 function, f, such that
f(x) = f(x a)
Classical algorithm: O(pN)
Queries to the oracle (probabilistically)
Quantum algorithm:
O(n) Queries to the oracle
MULT90063 Introduction to Quantum Computing
Grover’s Algorithm
• Unordered search, find one marked item among many
• Classically, this requires N/2 uses of the oracle
• Quantum mechanically, requires only O(√N).
|0i |0i |0i |0i
Inversion (I-2|0><0|) MULT90063 Introduction to Quantum Computing Shor’s algorithm • Efficientquantumalgorithmsforfactoringsemiprime numbers • Bestknownclassicalalgorithmisnumberfieldsieve (exponential in bit-length). • UnderpinstheRSAcryptosystem • HiddenSubgroupProblems(eg.Discretelogarithm)similar. Shor, Proc 35th of Comp Sci, 26, (1995) MULT90063 Introduction to Quantum Computing Quantum Supremacy: Boson Sampling Beamsplitters Wall Photon out Path of a photon MULT90063 Introduction to Quantum Computing IQP Circuits (5) Measure (1) Hadamard gates Equal superposition (2) Random single qubit phases (3) Random two qubit phase gates between every pair (4) Interfere all the resulting states MULT90063 Introduction to Quantum Computing Pseudo-random Circuits Hadamards to give equal superposition Controlled-Z gates to provide entanglement in a regular pattern A random single qubit gate between every pair of CZ gates. MULT90063 Introduction to Quantum Computing Errors in Quantum Devices Physics 90045 Lecture 12 MULT90063 Introduction to Quantum Computing Purity for one qubit If the distance from the origin to the state is measured to be r, the purity is: P = 1 + r2 2 Maximum purity of 1 for all pure states. Minimum purity of 1⁄2 for a completely mixed state. |0i |1i p2 hYi |0i + i|1i |0i i|1i p2 |0i + |1i p2 Note: There’s a more technical definition of purity in terms of density matrices, which we won’t cover in this course. MULT90063 Introduction to Quantum Computing Randomized Benchmarking How good are our gates individual gate? We want a number for how much error doing each operation is. One way of determining this is to perform randomized benchmarking. Apply a random sequence of gates Make a measurement: Should measure 0 Apply the inverse of the whole sequence MULT90063 Introduction to Quantum Computing Quantum Error Correction Similar to classical error correction codes, we can have a quantum repetition code: |0i ! |000i |1i ! |111i In particular, a quantum superposition would be encoded as: ↵ |0i + |1i ! ↵ |000i + |111i Two key differences between quantum and classical error correction codes: 1. Cannot measure the codewords directly; would collapse the state 2. Phase errors “Logical 0” “Logical 1” MULT90063 Introduction to Quantum Computing The Surface Code l A topological code suited to solid state (Kitaev 1997, Raussendorff 2007) l A remarkably high threshold of ~1% (Wang et al, 2011) u Parallel and synchronous control required MULT90063 Introduction to Quantum Computing Optimization Problems Given some cost-function or “objective function” we would like to maximize/minimize. Often the inputs/parameters are constrained. Optimal value Cost function Parameters MULT90063 Introduction to Quantum Computing Number partitioning as a QUBO problem But if we square, we should get a positive solution (or zero). We want to find the assignment of spins which has the minimum energy (ie. closest to zero): X!2X X2 H = wiZi = 2wiwjZiZj + wi I i i6=j i Coupling is the product of numbers Eg. For the set {1, 2, 3}: 2 H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I Finding minimum energy state will solve the problem! MULT90063 Introduction to Quantum Computing (1)Prepareatrialstate| (✓)i on the quantum computer, where θ can be any adjustable gate parameter. (2) Measure the expectation value of the energy, E. (3) Use a classical optimization technique such as the Nelder–Mead simplex method, determine new values of θ that decrease E. Repeat these steps until the value of the energy converges QUI/Quantum Computer MULT90063 Introduction to Quantum Computing Adiabatic Quantum Computation H(s) = (1 s)Hx +sHp s = t/T System is originally in the state: Hx = X Hp = Z “Landau-Zener” avoided crossing System ends up in Time the state: MULT90063 Introduction to Quantum Computing HHL Algorithm - HHL algorithm solves systems of linear equations - Need a method for emulating exp(iAt) - Can be used as a quantum subroutine - Has a runtime, exponentially faster than classical versions. MULT90063 Introduction to Quantum Computing Quantum Complexity Classes Quantum Complexity Classes Classical Complexity Classes MULT90063 Introduction to Quantum Computing Questions? MULT90063 Introduction to Quantum Computing MULT90063 Introduction to Quantum Computing Lecture 23 Quantum Computing architectures and quantum complexity classes Lecture 24 Quantum Computing Review HHL algorithm using the QUI 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com