Overview

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

Note this assignment has 110 points (your final score is x/100 where x is the points you earned)

---

This is an overview of your path through the quantum computing section. In this section, you will put together all the tools necessary to build a quantum computing emulator which will then be used to simulate Shor’s Algorithm and factor 15 (or maybe even 55).

Shor’s Algorithm

Week 1: Build a quantum computing simulator

• Dirac Notation (10 points)

• Quantum Computing Simulators

  • Simulator S (8 points)

  • Simulator M : (8 points)

  • Measuring (4 points)

• Non-atomic Gates (10 points)

Notes about Week 1: Your goal in week 1 is to put together a working simulator including a “compiler” which takes the gates you want to use into primitive gates. You only need simulator I working to continue on and if you are at the end of week 1 and have this simulator working you should continue!

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)

• Quantum Matrix (10 points)

• Controlled Modular Multiplication (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.