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 Implementations and Complexity Classes
Lecture 23
MULT90063 Introduction to Quantum Computing
Implementations
MULT90063 Introduction to Quantum Computing
Different Quantum Computing Hardware
Different ways to implement a quantum computer:
– Ion Traps
– Superconducting qubits
– NV centres
– Quantum Optics
– Semiconductors: Donors and Dots
MULT90063 Introduction to Quantum Computing
Image: (Innsbruck). Electrodes to trap six 40Ca ions. Ions are laser cooled, and can remain in the trap for days once cooled. Qubit manipulation and readout via laser, CCD camera.
MULT90063 Introduction to Quantum Computing
Ion Traps (2)
The Qubit: Quantum states of trapped ions (typically 40Ca), interacting via coupling to collective degree of freedom.
Number of Qubits Demonstrated: ~20-50 Fidelity reported: 99.9%
• Largest number of high fidelity qubits
• Extremely high fidelity
• Demonstrated error correction code (7 qubit) and largest “genuine” demonstration of
Shor’s algorithm. Fault Tolerant QEC demonstration.
Challenges:
• Transport of qubits
• Comparatively large, slow • Heating
Corportate support
IonQ, Alpine
MULT90063 Introduction to Quantum Computing
Paper on measured error rates for ion traps
Sepiol et al, PRL, 123, 110503, (2019)
MULT90063 Introduction to Quantum Computing
Superconducting Qubits
(UCSB) Showing five (transmon or Xmon) superconducting qubits placed in a row, each coupled to their neighbour. Information is stored in the charge/phase degrees of freedom.
MULT90063 Introduction to Quantum Computing
Superconducting Qubits (2)
The Qubit: The charge or phase degrees of freedom of superconducting circuits. Modern designs (transmon qubits) minimize noise.
Number of Qubits Demonstrated: ~50+ Fidelity reported: 99.4%
• Large number of qubits
• Demonstrated transport
• Demonstrated genuine error supression in five and nine qubit error correction
Challenges:
• Comparatively fast decoherence times • Currently comparately large
Corportate support
Google, IBM, Rigetti
MULT90063 Introduction to Quantum Computing
Quantum supremacy
Google’s quantum supremacy paper, September 20, 2019
MULT90063 Introduction to Quantum Computing
Quantum Optics
Image from Pryde ( ). Quantum states of light are used to represent quantum information, and manipulated using linear optics. First proposed by KLM, using entanglement generated by non-linear crystals, and subsequent linear optical operation.
MULT90063 Introduction to Quantum Computing
Linear Optics (2)
The Qubit: The optical quantum states of light, including continuous variables, squeezed states, polarization and presence or absence of photons.
• Communications and telecommunication applications
• Qubits impervious to their environment
• May demonstrate quantum advantage with Boson sampling
Challenges:
• Interacting large numbers of qubits
• Creating large quantum states
• Single photon sources
MULT90063 Introduction to Quantum Computing
Generation of multi-qubit cluster states
Asavanant et al, Science, 366, 6463, p373-376, 2019
MULT90063 Introduction to Quantum Computing
NV Centres
Nitrogen Vacancy centre in diamond forms a room temperature, electronic spin-1 system which can be manipulated with microwave fields, and read out optically.
Image: Ahanovic et al Nature Photonics, 2011
MULT90063 Introduction to Quantum Computing
NV Centres (2)
The Qubit: The electronic spin-1 system of an NV defect in diamond. Can be coupled to nearby nuclear spins.
Number of Qubits Demonstrated: 10 Fidelity reported: 99.2%
• Room temperature
• Biologically compatible
• First loophole-free violation of Bell’s inequalities (Delft)
Challenges:
• Coupling two NVs is difficult
• Diamond difficult to work with, scale
MULT90063 Introduction to Quantum Computing
NV quantum memory
MULT90063 Introduction to Quantum Computing
Semiconductor Donors and Dots
UNSW. Qubits are the states of individual donors (either electron or nuclear spins) or the electronic levels of quantum dots (act as artificial atoms).
MULT90063 Introduction to Quantum Computing
Donors and Dots (2)
The Qubit: The electrons spin or nuclear spin degrees of freedom of a donor or a dot. Number of Qubits Demonstrated: 3+
Fidelity reported: > 99%
• Intrinsically extremely long decoherence times (3s/minutes)
• Existing semiconductor industry at scale
• Comparatively small
Challenges:
• Need more qubits and coupling
Company support
Intel, Commonwealth Bank, Telstra
MULT90063 Introduction to Quantum Computing
Donors: A two qubit swap gate
He et at, Nature, 571, 371-375 (2019)
MULT90063 Introduction to Quantum Computing
Quantum Complexity Classes
MULT90063 Introduction to Quantum Computing
Some classical complexity classes
P: Problems which can be solved in polynomial time NP: Problems which can be checked in polynomial time
(ie. they have an efficiently verifiable proof)
#P: Problems which count the number of solutions in NP
What are the equivalent for quantum computers?
MULT90063 Introduction to Quantum Computing
Complexity classes with error
BPP is Bounded error Probabilistic Polynomial time. Polynomial time, but on a probabilistic computer allowing for an error of as much as 1/3.
– Can flip coin and make random decisions
– Guaranteed to run in polynomial time
– On any given run of the algorithm has a probability <1/3 of
the wrong answer, whether the answer is TRUE or FALSE.
MULT90063 Introduction to Quantum Computing
Bounded error Quantum Polynomial Time
BQP is the set of decision problems solvable by a quantum computer in polynomial time, with an error of at most 1/3.
MULT90063 Introduction to Quantum Computing
Polynomial Time Algorithms
So BQP is (roughly, including error) the quantum equivalent of P/BPP. What’s the analogy to NP?
MULT90063 Introduction to Quantum Computing
QMA and QMA Complete
Quantum Merlin-Arthur (QMA) is the analog of NP.
Informally:
NP is the set of problems you can verify in polynomial time.
QMA is the set of problems you can verify in polynomial time with a quantum “proof”.
Example: Is does the lowest energy eigenstate of local Hamiltonian H have an energy less than Ea or are all the energies greater than Eb?
Verification uses a quantum state as a “proof”, and measure the energy!
QMA Complete: The hardest problems in QMA. Can map any problem in QMA onto these.
MULT90063 Introduction to Quantum Computing
“Stoquastic” MA
Not all Hamiltonians are equally hard to find the ground state of. In fact, those we have using for quantum annealing are easier in comparison to a general local Hamilonian. These types of Hamiltonians are known as stoquastic Hamiltonians, and have their own complexity class:
Technically, a Stoquastic matrix is a Hermitian matrix, where all off-diagonal elements are real and non-positive.
Clearly, since we’ve been encoding NP- complete problems like MAX-CUT StoqMA includes NP.
MULT90063 Introduction to Quantum Computing
Fitting it all together
Quantum Complexity Classes
Classical Complexity Classes
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