在计算复杂理论中，总是会有一些人为定义的抽象问题。
Simon问题的输入函数以f：n→m的形式为正整数 n和m。为了简单起见，我们可以将注意力限制在M = N 的情况下，但是在做出这一假设方面没有什么可获得的 - Simon的算法及其分析基本相同。
我们将解开承诺以更好地理解暂时说什么，但是在这样做之前，让我们清楚地表明，大多数功能都无法满足这一Promise；它要求F具有非常特殊的结构。同样重要的是要注意，如果实现承诺，只能有一个有效的字符串。因此，对于满足承诺的功能，总有一个独特的正确答案。
为了更好地理解Promise，考虑两种主要情况是有帮助的：第一种情况是S是全零字符串，，第二种情况是S不是全零字符串。
问题定义
我们有一个二进制函数：
f:{0,1}n→{0,1}m
满足：
f(x)是 2-to-1，即对于某个隐藏的 s，我们有：
f(x)=f(x⊕s)
这意味着 f(x) 的值每次都重复两次，一个在 x，一个在 x⊕s.
解的结构
- 测量后的方程组
- Simon 算法执行后，我们得到 n−1n-1n−1 个独立的线性方程： y1⋅s1⊕y2⋅s2⊕...⊕yn⋅sn=0
- 这些方程给出一个线性方程组，求解这个系统能得到唯一的非零 s（除非 s 在一个更大的子空间中）。
- 唯一性分析
- 由于 Simon 算法随机采样多个独立的测量结果（每次都会产生一个独立的 y 值），我们最终得到一个具有 n−1n-1n−1 个独立方程的系统： As=0其中 A 是一个满秩的 (n−1)×n 矩阵（模 2 运算）。
- 这个系统的解是一个 1 维线性子空间，即 s 只能是一个固定的方向。
- 由于 s≠0（根据 Simon 问题的定义），解空间只有一个非零向量。
结论：
- sss 是唯一的（如果要求 s≠0s \neq 0s=0）。
- 如果我们允许多个周期存在，那么解的集合可能是更高维的子空间。
代码验证：qiskit>1.0.0
定义Simon函数
# import random Simon algorithm!!!
import qiskit.quantum_info as qi
from qiskit import QuantumCircuit
import numpy as npdef simon_function(s: str):"""Create a QuantumCircuit implementing a query gate for Simon problem obeying the promise for the hidden string `s`"""# Our quantum circuit has 2n qubits for n = len(s)n = len(s) #means stringqc = QuantumCircuit(2 * n) #the former n qubits store x,the latter n qubits store f(x)# Define a random permutation of all n bit strings. This permutation will effectively hide the string s.pi = np.random.permutation(2**n) # pi is a length of 2^n random array for simulating random binary number. # Now we'll define a query gate explicitly. The idea is to first define a function g(x) = min{x,x ^ s}, which# is a simple function that satisfies the promise, and then we take f to be the composition of g and the random# permutation pi. This gives us a random function satisfying the promise for s.query_gate = np.zeros((4**n, 4**n)) #because it is the 2^(2n)for x in range(2**n):for y in range(2**n):z = y ^ pi[min(x, x ^ int(s, 2))] query_gate[x + 2**n * z, x + 2**n * y] = 1# Our circuit has just this one query gateqc.unitary(query_gate, range(2 * n))return qc定义Simon测量函数
from qiskit_aer import AerSimulator
from qiskit import ClassicalRegisterdef simon_measurements(problem: QuantumCircuit, k: int):"""Quantum part of Simon's algorithm. Given a `QuantumCircuit` thatimplements f, get `k` measurements to be post-processed later."""n = problem.num_qubits // 2qc = QuantumCircuit(2 * n, n)qc.h(range(n))qc.compose(problem, inplace=True)qc.h(range(n))qc.measure(range(n), range(n))result = AerSimulator().run(qc, shots=k, memory=True).result()return result.get_memory()打印结果
display(simon_measurements(simon_function("11011"),k=12))这个问题理解起来需要一点时间。
对于 Simon 问题，函数 f(x)f(x)f(x) 需要满足：
- 对于任何
x，函数值f(x)只会和f(x ⊕ s)相等。 - 所有可能的
x都会分成2^(n-1)对，使得f(x) = f(x ⊕ s)。
具体映射方式如下：
- 设
s是 隐藏的周期字符串，长度为n，它是固定的。 - 我们定义一个随机分组方式：
- 对于每个
x，我们定义一个映射g(x)： g(x)=min(x,x⊕s)g(x) = \min(x, x \oplus s)g(x)=min(x,x⊕s)- 这里
min(x, x ⊕ s)选择较小的x作为函数的基础输入。
- 这里
- 然后
f(x)是g(x)经过 随机置换π(g(x))之后的结果： f(x)=π(g(x))f(x) = \pi(g(x))f(x)=π(g(x)) - 这样确保了 每个
x和x ⊕ s具有相同的f(x)值，从而满足f(x) = f(x ⊕ s)。
- 对于每个
示例 1：n = 3, s = "110"
假设：
n = 3（即x为 3 位二进制数）。- 隐藏的
s = "110"（即s = 6）。 - 设定 随机置换
π(g(x))。
构造 f(x)满足：
f(x)=f(x⊕s)
解释：
- 这里
π(g(x))是一个随机映射，使得每个g(x)都有唯一的f(x)值。 - 同组的
x和x ⊕ s具有相同的f(x)值（如000&110共享5，001&111共享2）。
代码实现
import numpy as npdef simon_function(s: str):n = len(s)pi = np.random.permutation(2**n) # 生成 2^n 大小的随机映射f_map = {}for x in range(2**n):x_s = x ^ int(s, 2) # 计算 x ⊕ sg_x = min(x, x_s) # 找到 g(x)if g_x not in f_map:f_map[g_x] = pi[g_x] # 进行随机映射f_x = f_map[g_x] # 确保 f(x) = f(x ⊕ s)print(f"f({bin(x)[2:].zfill(n)}) = f({bin(x_s)[2:].zfill(n)}) = {f_x}")# 示例：n = 3, 隐藏周期 s = "110"
simon_function("110")
