Overview

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

Note this assignment is out of 110 points (so you final score is x/110 where x is the points you earned)

Shor’s Algorithm

Week 1: Build a quantum computing simulator

• Dirac Notation (10 points)

• Quantum Computing Simulator II (10 points)

  • Quantum Computing Simulator I(abcd) : (10 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)

Week 3: Shor’s Algorithm

• Classical Shor’s (10 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)

Extra Credit Options: There are various circuit subroutines you might want to build.

One of these is to build a quantum circuit for an arbitrary classical circuit: Classical Gates 10 extra credit points

Another useful circuit primitive is to be able to generate Controlled Gates. 5+5 extra credit points

Finally, you can explicitly show that BQP is in PSPACE: BQP in PSPACE. This is not that hard and I think conceptually very interesting so it’s probably worth doing if you have some extra time. 20 extra credit points.

I also have some extra credit options for Quantum Error Correction and Understanding Physical Qubits that I haven’t finished writing up. Let me know if either of these are of interest to you.

---

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