Contents

Overview

Overview

This is slightly updated content. For the original Spring 2022 version of this content click below

https://courses.physics.illinois.edu/phys498cmp/sp2022/secure/1-QuantumComputing/html/Overview.html

Here is an overview of paths through the quantum computing section.

Anything which is extra credit should be skipped until the end. Nothing cumulatively builds on these and so to reach the plateau of this assignment and to maximize points you should leave them until the end!

Template for Solution Document: https://docs.google.com/document/d/16SjjSvR1M8UsBODIqGr59LBb-UaDIEG_1CzB4-wrKeY/edit

Shor’s Algorithm

Week 1: Build a quantum computing simulator

  • Dirac Notation (10 points)

  • Quantum Computing Simulator I(abc) (20 points)

    • Quantum Computing Simulator II : (5 points)

    • Quantum Computing Simulator III (Extra Credit: 5 points)

  • Non-atomic Gates (10 points)

Week 2: Master Phase Estimation

  • Phase Estimation (20 points + 10 points for QFT below)

    • Quantum Fourier Transform (10 points) (you will have to pause to build this during the phase-estimation section)

      • Understanding the QFT (Extra Credit: 2 points)

Week 3: Shor’s Algorithm

  • Classical Shor’s (10 points)

    • How fast is classical Shor’s (Extra Credit: 2 points)

  • A Unitary Matrix whose eigenvalues have the period of period-finding (10 points)

  • Adding classical (and controlled-classical) gates to your simulator (10 points)

  • Shor’s Algorithm (10 points)

Universality

We have heard that you can build any unitary matrix \(U\) from H,P, CNOT. Work through here how this works:

  • Universal Gates (Extra Credit: 5 points)

More Circuits

  • Circuits (Extra Credit: 2 points)

Other Extensions

None of these are written yet but with a little googling you could do them.

  • Quantum Algorithms:

    • Use your quantum simulator to simulate and learn about Grover’s Algorithm

    • Use your quantum simulator to simulate Quantum Counting

    • Use your quantum simulator to do time-evolutiomn of quantum systems and use phase estimation to find their ground states.

      • Spins

        • A single spin in a magnetic field

        • Two spins in a magnetic field

        • Two spins with a Heisenberg coupling between them

      • Hopping Electrons

        • A tight binding model

        • Add some interactions

      • Quantum Chemistry

      • Hamiltonian Simulation: There are a huge number of works on simulating Hamiltonians.

        • Trotter breakup

        • Graph Color Breakup

        • Fractionalized excitations

      • Quantum Variational Approaches

  • How powerful are quantum computers?

    • (Subsets of ) quantum computers are weak. Write a classical simulator which simulates

      • Circuits which stay low in entanglement

        • Circuits with no two-qubit gates

        • Circuits with low entanglement

      • \(H^n\) plus CNOT and phase gates and toffelli

      • Stabilizer circuits

      • Match Gates

    • Quantum computers are not too powerful (i.e. BQP in PSPACE)

  • Entanglement, Causality, and reduced density matrices

  • Adiabatic Quantum Computing for optimization and state preparation

  • Quantum Protocols:

    • Quantum Key Distribution

    • Teleportation

  • Quantum Error Correction

  • Helpful Tools

    • Visualization

    • Manipulate dirac notation symbolically (this is useful for checking a bunch of the formulas we use)

  • Random Things:

    • Deferred Measurement

    • Zenos Paradox

  • Understand how we can actually build these gates physically from quantum systems

previous

Other Interesting Automata

next

Dirac Notation