Skip to content

Instantly share code, notes, and snippets.

View Strilanc's full-sized avatar

Craig Gidney Strilanc

741 followers · 0 following
View GitHub Profile
@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 / 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
@Strilanc
Strilanc / add_cut_noise.py
Last active February 3, 2023 14:24
Adds noise to gates crossing a cut.
from typing import Optional, Dict
import stim
q2_gates = {
'CNOT',
'CX',
'CY',
'CZ',
'ISWAP',
@Strilanc
Strilanc / agree-to-disagree-flytrap.json
Created October 16, 2022 22:54
{
"name": "Virtual Lab: New Experiment",
"grid": {
"width": 13,
"height": 10,
"pieces": [
{
"coord": {
"x": 0,
"y": 1