The 'Try All Inputs at Once' Myth

// main.go
package main

import (
	"fmt"
	"math"
	"math/rand"
)

// kronecker product of two matrices (represented as flat slices with given dimension)
func kron(A []complex128, aRows, aCols int, B []complex128, bRows, bCols int) ([]complex128, int, int) {
	rows := aRows * bRows
	cols := aCols * bCols
	C := make([]complex128, rows*cols)
	for i := 0; i < aRows; i++ {
		for j := 0; j < aCols; j++ {
			for k := 0; k < bRows; k++ {
				for l := 0; l < bCols; l++ {
					C[(i*bRows+k)*cols+(j*bCols+l)] = A[i*aCols+j] * B[k*bCols+l]
				}
			}
		}
	}
	return C, rows, cols
}

// Hn builds the n-qubit Hadamard matrix via iterated Kronecker products
func Hn(n int) ([]complex128, int) {
	s := 1.0 / math.Sqrt2
	H := []complex128{complex(s, 0), complex(s, 0), complex(s, 0), complex(-s, 0)}
	M := []complex128{1}
	mRows, mCols := 1, 1
	for i := 0; i < n; i++ {
		M, mRows, mCols = kron(M, mRows, mCols, H, 2, 2)
	}
	_ = mCols
	return M, mRows
}

// matrix-vector multiply: M (dim x dim) times v (dim)
func matvec(M []complex128, dim int, v []complex128) []complex128 {
	out := make([]complex128, dim)
	for i := 0; i < dim; i++ {
		for j := 0; j < dim; j++ {
			out[i] += M[i*dim+j] * v[j]
		}
	}
	return out
}

func main() {
	n := 4
	dim := 1 << n // 2^n = 16

	// Build H^n
	M, _ := Hn(n)

	// |0...0> state vector
	start := make([]complex128, dim)
	start[0] = 1

	// Apply H^n
	psi := matvec(M, dim, start)

	// Compute probabilities |a|^2
	probs := make([]float64, dim)
	for i, a := range psi {
		probs[i] = real(a)*real(a) + imag(a)*imag(a)
	}
	fmt.Printf("after H^%d on |0...0>: each of the %d amplitudes has |a|^2 = %.4f\n", n, dim, probs[0])

	// Simulate measurement: sample x uniformly at random (seed 0 for reproducibility)
	rng := rand.New(rand.NewSource(0))
	shots := 2000
	counts := make([]int, dim)
	for i := 0; i < shots; i++ {
		// weighted sample via CDF
		r := rng.Float64()
		cum := 0.0
		chosen := dim - 1
		for x, p := range probs {
			cum += p
			if r < cum {
				chosen = x
				break
			}
		}
		counts[chosen]++
	}
	fmt.Printf("empirical fractions over 2_000 shots, first 4: [%.3f %.3f %.3f %.3f]\n",
		float64(counts[0])/float64(shots),
		float64(counts[1])/float64(shots),
		float64(counts[2])/float64(shots),
		float64(counts[3])/float64(shots),
	)
	fmt.Println("=> measurement gives a uniformly random x, not f(all x)")
}