Problem 456773 · hard · Quantum Computing · Level 04 Oracles and Search

Twin Inputs in the Lab Notebook

Simon's problem · linear algebra over GF(2) · Gaussian elimination · XOR · bit strings

A function f on n bits hides a string s: two different inputs give the same output exactly when they differ by s, that is f(x) = f(x') if and only if x' = x or x' = x \oplus s (\oplus is bitwise XOR). When s is all zeros, f never repeats an output. Each run of Simon's quantum circuit on f ends with a measured string y of n bits that satisfies

y\cdot s = (y_0s_0 + y_1s_1 + \dots + y_{n-1}s_{n-1}) \bmod 2 = 0,

where y_k and s_k are character k of the strings (qubit 0 is the leftmost character). The lab notebook ys lists the strings measured in several runs; it may repeat a string or contain the all-zeros string.

The notebook has been kept long enough that it pins down s: either exactly one string z other than all zeros satisfies y\cdot z = 0 for every y in ys (then s = z), or none does (then s is all zeros). Write simon_secret(n, ys) that returns s as a string of n characters "0"/"1".

The larger tests use the helper simon_log(n, seed), which picks a hidden s from seed and returns a notebook of measured strings that pins it down; you may use it with Run.

Examples

Input:  n = 3, ys = ["011", "100"]
Output: "011"
Explanation: "100" forces s0 = 0 and "011" forces s1 = s2; the only choice
besides "000" is "011".

Input:  n = 2, ys = ["11", "00", "11"]
Output: "11"

Input:  n = 3, ys = ["110", "011", "111"]
Output: "000"

Constraints

  • 1 <= n <= 40, 1 <= len(ys) <= 200; each string has length n
  • trying all 2^n candidates is far too slow for the largest n

Goals

  • Turn measured strings y with y . s = 0 (mod 2) into a system of linear equations over GF(2)
  • Solve it by elimination with XOR instead of searching all 2^n candidates
  • Recognise when only the all-zeros string solves it
Starting Python…