Dirty Period Finding with 2n+1 qubits

This repository contains code for generating and validating the constructions from my preprint "Factoring with n+2 clean qubits and n-1 dirty qubits".

Table of Circuit Constructions

Name	In Paper	In Code	In Quirk
Find Period	fig 2, 3, 4	???	period-find-output
Bimultiply mod R	fig 5	modular_bimultiplication_rules.py	???
Scaled-Add mod R	fig 6	modular_scaled_addition_rules.py	???
Double mod R	fig 7	modular_double_rules.py	double-mod-effect
Pivot-flip	fig 8, 9	pivot_flip_rules.py	???
Add mod R	fig 10, 11, 12	modular_addition_rules.py	???
Negate mod R	fig 13	modular_negate_rules.py	???
Compare	fig 14	comparison_rules.py	???
Add	fig 15, 16, 17, 18	addition_rules.py offset_rules.py	big-add-test control-add-test
Increment	fig 19, 20	increment_rules.py	???
No-Ancilla Increment	fig 21	bootstrap_ancilla_rules.py phase_gradient_rules.py	full-increment-test
Rotate Bits	fig 22	rotate_bits_rules.py	???
Reverse Bits	fig 23	reverse_bits_rules.py	???
Multi-Not	fig 24 25	multi_not_rules.py	???
Overview	fig 1	-	-

Development Environment

These instructions explain the steps involved in getting the code from this repository to run on an Ubuntu machine. The example commands have been tested and confirmed to work on Ubuntu 16.10 booted from a live CD.

0. Have git and pip installed.

   sudo add-apt-repository universe

   sudo apt-get update

   sudo apt-get install --yes git python-pip

1. Clone this repository.

   git clone https://github.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding.git

2. Install python dependencies.

   sudo -H pip install pybind11

   sudo -H pip install -r requirements.txt

3. (Optional) Run tests and example code.

   cd PaperImpl-2017-DirtyPeriodFinding

   pytest

   python src/factor.py 55

   python src/count_gates.py

4. Edit away