Skip to content

Instantly share code, notes, and snippets.

View Strilanc's full-sized avatar

Craig Gidney Strilanc

743 followers · 0 following
View GitHub Profile
@Strilanc
Strilanc / hastings_stim_pymatching.py
Created July 12, 2021 00:02
Estimating the threshold of a new quantum code using stim and pymatching.
import csv
import pathlib
import time
from dataclasses import dataclass
from typing import Callable, List, Dict, Any, Set, FrozenSet, Iterable, Tuple
import math
import pymatching
import networkx as nx
import stim
import matplotlib.pyplot as plt
@Strilanc
Strilanc / fast_geo_rng.cc
Created February 2, 2025 22:53
Implements a class that can quickly approximately sample from geometric distributions whose miss probabilities are specified as an integer root of 1/2. For example, for p=0.1% you would use the 693'th root because 1 - 0.5^(1/693) ~= 0.1%.
#include <chrono>
#include <iostream>
#include <random>
#include <bit>
#include "immintrin.h"
#include <algorithm>
__m256i countl_zero_vec(__m256i x) {
// Tried doing vectorized bit twiddling instead, but it was slower.
@Strilanc
Strilanc / increment_to_linear_toffoli.py
Created June 9, 2015 05:54
Hacky python code to build n-bit reversible increment gates out of O(n) Toffoli gates and one ancilla bit.
# coding=utf-8
import math
import itertools
def evaluate_circuit(gates, initial_bits=None):
"""
:param gates: [( [controls], [targets] )]
:param initial_bits: set(on_bits)
@Strilanc
Strilanc / hacky_postselection_analysis.py
Created April 3, 2024 21:47
What happens when I postselect the single-round data from the public google 3v5 experimental data?
import collections
import numpy as np
import sinter
import stim
import pathlib
from matplotlib import pyplot as plt
workspace = pathlib.Path("google_qec3v5_experiment_data")
@Strilanc
Strilanc / chsh_v3.lean
Created December 10, 2023 04:41
Another iteration on shortening the CHSH proof.
import Mathlib.Data.Nat.Basic
import Mathlib.Tactic.Linarith
----------------- DEFINE PROBABILITY --------------------
structure Chance where
p : Rat
v : (p >= 0) ∧ (p <= 1)
def Chance.le (a b : Chance) : Bool := a.p <= b.p
infixl:45 " ≤ " => Chance.le
@Strilanc
Strilanc / chsh_v2.lean
Created December 7, 2023 03:24
Shorter proof of CHSH (377 lines instead of 514 lines)
import Mathlib
import Mathlib.Data.Nat.Basic
import Mathlib.Data.Rat.Basic
import Mathlib.Data.Rat.Order
theorem le_pin (a b : Nat) (h1 : a <= b) (h2 : b <= a)
: a = b
:= by
apply Nat.eq_or_lt_of_le at h1
cases h : (decide (a = b))
@Strilanc
Strilanc / chsh.lean
Last active December 6, 2023 13:59
A lean proof of the CHSH inequality. More accurately: a terrible lean proof of the CHSH inequality, made by a complete beginner with no idea what they are doing. But the compiler accepts it!
import Mathlib
import Mathlib.Data.Nat.Basic
import Mathlib.Data.Rat.Basic
import Mathlib.Data.Rat.Order
----------------- BASIC DATA TYPES AND COMBINATORS --------------------
structure Odds where
lose : Nat
win : Nat
valid : (lose != 0) ∨ (win != 0)
@Strilanc
Strilanc / zalka_half_workspace_mod_mult.py
Created April 24, 2023 04:12
An implementation of the half-workspace modular multiplication described in https://arxiv.org/pdf/quant-ph/0601097.pdf
import math
from typing import Union
from typing import Tuple
def zalka_imul_mod_low_workspace(*, dst: 'Quint', factor: int, modulus: int) -> None:
"""Performs an inplace modular multiplication using n/2 + O(1) workspace."""
assert factor < modulus
assert math.gcd(factor, modulus) == 1
assert len(dst) >= modulus.bit_length() * 3 // 2 + 2
@Strilanc
Strilanc / fraction_fourier_hilbert.py
Last active April 16, 2023 21:06
Interpolates between drawing a hilbert curve and the fourier transform of a hilbert curve
import math
from numpy import array, hstack, vstack
import numpy as np
from PIL import Image
# these two methods were copied from https://github.com/dmishin/fft-image-experiments
def hilbert_indices(N):
"""Genrate 2^N x 2^N integer array, filled with values from 0 to 4^N along hilbert curve"""
m = array([[0]], dtype=np.int)
@Strilanc
Strilanc / first_manim_rep_code.py
Created March 8, 2023 22:12
Using manim to make a rep code animation.
from manim import *
class SquareToCircle(Scene):
def construct(self):
n = 5
h = n // 2
bits = [MathTex("0") for k in range(n)]
bits2 = [MathTex(f"b_{{{k+1}}}") for k in range(n)]
dt = 20