首页 交叉学科 量子计算

在下文中，我们将回顾一些针对 Codeforces 上的 Microsoft Q# 夏季 2018 和冬季 2019 编码竞赛的 Silq 解决方案。 针对 Q# 程序员的详细解决方案可在 2018 年和 2019 年获得。

# 生成零态和基态的叠加态

任务的原始来源：问题 A2（2018）

给定经典位 b∈𝔹nb\in 𝔹^n 且 b[0]=1b[0]=1 ，返回态 12(∣b⟩+∣0⟩)\frac{1}{\sqrt{2}}\Big(\ket{b}+\ket{0} \Big) ，其中 ∣0⟩\ket{0} 代表使用 nn 位。

# 解决方案

以下解决方案特别有用

  • 矢量（ 𝔹^n ）
  • 哈达玛(Hadamard)变换(transform)（ H ）
  • 内联条件（ if-then-else ）
  • 类型注释（ 0:𝔹 ）
  • 类型转换（ as int[n] 和 as 𝔹^n ）
  • forget
def solve[n: !ℕ](bits: !𝔹^n) {
  // prepare superposition between 0 and 1
  x := H(0: 𝔹);
  // prepare superposition between bits and 0
  qs := if x then bits else (0: int[n]) as 𝔹^n;
  // uncompute x
  forget(x=qs[0]); // valid because `bits[0]==1`
  return qs;
}
// EXAMPLE CALL
def main() {
  // example usage for bits=1, n=2
  x := 1: !int[2];
  y := x as !𝔹^2;
  return solve(y);
}
# 生成 W 态
任务的原始来源：问题 A4（2018）
在量子位 N=2kN=2^k 下生成一个广义 W 态：
WN=1N(∣100...0⟩+∣010...0⟩+...+∣00...01⟩)W_N = \frac{1}{\sqrt{N}} \Big( \ket{100...0}+\ket{010...0} + ...+\ket{00...01}\Big)
# 解决方案
以下解决方案特别有用
  • λ 抽象（ λ... ）
def solve(k:!ℕ) {
  // produce uniform superposition over k-bit uints
  i:=0:uint[k];
  for j in [0..k){ i[j]:=H(i[j]); }
  // invert i-th qubits (results in correct state, but entangled with i)
  qs:=vector(2^k,0:𝔹);
  qs[i]=X(qs[i]);
  // uncompute i
  forget(i=λ(qs:𝔹^(2^k))lifted{ // function to reconstruct i from qs
    i:=0:uint[k];
    for j in [0..2^k){
      if qs[j]{ // in the superposition's summand where qs[j]==1, i==j
        i=j as uint[k];
      }
    }
    return i;
  }(qs));
  // return result
  return qs;
}
// EXAMPLE CALL
def main() {
  // example usage for k=2
  return solve(2);
}
# 区分 3 量子位状态 (Distinguish 3-qubit States)
任务的原始来源：问题 B1（2019）
确定给定的量子位是否处于状态 ψ0\psi_0（返回 00 ）或 ψ1\psi_1（返回 11 ）：
  • ψ0=13(∣100⟩+ω∣010⟩+ω2∣001⟩)\psi_0=\frac{1}{\sqrt{3}}\Big(\ket{100}+\omega\ket{010}+\omega^2\ket{001}\Big) ，其中 ω=e2iπ/3\omega=e^{2i\pi/3} 。
  • ψ1=13(∣100⟩+ω2∣010⟩+ω∣001⟩)\psi_1=\frac{1}{\sqrt{3}}\Big(\ket{100}+\omega^2\ket{010}+\omega\ket{001}\Big) ，其中 ω=e2iπ/3\omega=e^{2i\pi/3} 。
你可以任意修改给定的量子比特（包括测量值）。
# 解决方案
关键点：
  • ψ0⊥ψ1\psi_0\perp\psi_1 ：这两个态是正交的。
  • ψ0\psi_0 可以在 33 个量子位 W3W_3 上转换为 WW 态。这个过程转换 ψ1\psi_1 到某种态 ψ1′\psi_{1}^{\prime} 正交于 W3W_3 。
  • 我们可以从 ∣000⟩\ket{000} 生成 W3W_3 (参见上面的问题 A4)。反过来从从 W3W_3 生成 ∣000⟩\ket{000} 和一个从 ψ1′\psi_{1}^{\prime} 到 ∣000⟩\ket{000} 与之正交的态。
以下解决方案特别是有用：
  • 分解列表：( (head,)~tail:=qs )
  • 递归函数 ( reverse )
def toW[n:!ℕ](qs:𝔹^n)mfree:𝔹^n{
  // for a single bit, prepare |1⟩
  if n==1{ qs[0]:=X(qs[0]); }
  else if n>1{
    // split qs into head (first element) and tail (rest)
    (head,)~tail:=qs;
    // prepare first bit
    θ:=2·asin(1/sqrt(n)); // sin(θ/2)=1/sqrt(n), cos(θ/2)=sqrt((n-1)/n)
    head:=rotY(θ,head); // |0⟩ ↦ cos(θ/2)|0⟩ + sin(θ/2)|1⟩ = cos(θ/2) |0⟩ + 1/sqrt(n)|1⟩
    // prepare remaining bits
    if !head { tail := toW(tail); }
    // combine head and tail again
    qs:=(head,)~tail;
  }
  return qs;
}
def solve(qs:𝔹^3):!ℕ{
  // transform ψ₀ to W₃
  if qs[1]{ phase(-2·π/3); } // exp(2*i*π/3)*exp(i*-2*π/3)=1
  if qs[2]{ phase(-4·π/3); } // exp(4*i*π/3)*exp(i*-4*π/3)=1
  // map W₃ to |000⟩
  qs:=reverse(toW[3])(qs);
  // check if obtained |000⟩
  return measure(qs as int[3])!=0;
}
// EXAMPLE CALL
def generate_input_state(state:!𝔹){
  // prepare ψ_0 (state=false) or ψ_1 (state=true)
  qs:=vector(3,0:𝔹);
  qs:=toW[3](qs);
  if state{
    if qs[1]{ phase(4·π/3); }
    else if qs[2]{ phase(2·π/3); }
  }else{
    if qs[1]{ phase(2·π/3); }
    else if qs[2]{ phase(4·π/3); }
  }
  return qs;
}
def main(){
  // expected outcome: (0,1)
  // prepare both states
  ψ_0:=generate_input_state(false);
  ψ_1:=generate_input_state(true);
  check0:=solve(ψ_0);
  check1:=solve(ψ_1);
  return (check0,check1);
}
# 检查字符串是否是周期性的
原始任务来源：问题 C2（2019）
实现一个函数 solve 并签名 solve[n:!ℕ](x:𝔹^n):𝔹 ，和
solve(x⃗)={1ifx⃗is periodic0otherwise% <![CDATA[ \text{solve}(\vec{x})=\begin{cases} 1 & \text{if } \vec{x} \text{ is periodic} \\\\ 0 & \text{otherwise} \end{cases} %]]>
一系列长度为 nn 的字符串被认为是周期性的，且周期 PP ( 1≤P≤n−11\leq P\leq n-1 ) 如果所有 i∈0,…,n−P−1i\in{0,\dots,n-P-1} ，xi=xi+Px_i=x_{i+P} 。
# 解决方案
  • 当 y 和 z 是可覆盖的，自动计算它们。
def solve[n:!ℕ](x:𝔹^n)lifted{
  y:=0:𝔹;
  // Check all possible periods.
  // Periods with P<(n+1)/2 are implicitly detected by period 2P because P<=(n+1)/2-1 implies 2P<=n-1.
  for p in [(n+1) div 2..n){
    // check period p
    z := 1:𝔹;
    for i in [0..n-p){
      z&=x[i]==x[i+p];
    }
    y|=z;
  }
  return y;
}
// EXAMPLE CALL
def main(){
  // expected outcome: (0,1)
  ap:=solve((true,true,false));
  p:=solve((false,false,false));
  return (ap,p);
}
# X 翼战斗机 (X-wing Fighter)
任务的原始来源：问题 D3（2019）
实现统一操作 nn 个量子位，由主副对角线都是非零元素，而其他任何地方都是零元素的大小为 2n2^n 的方阵表示。
例如，对于 n=3n=3 ，操作的矩阵应当有如下形状：
X......X
.X....X.
..X..X..
...XX...
...XX...
..X..X..
.X....X.
X......X
这里 X 表示矩阵中的非零元素， . 表示矩阵中的零元素。
矩阵的行和列索引遵循小端格式：索引的最低有效位首先存储在量子位数组中。因此，矩阵的第二列为你提供了基态系数，如果你应用于基态 ∣10…0⟩\ket{10…0} 将会得到。
# 解决方案
关键点：一个可能的解决方案是将 ∣b1⋯bn⟩\ket{b_1 \cdots b_n} 映射到 12∣b1⋯bn⟩±12∣b1‾⋯bn‾⟩\frac{1}{\sqrt{2}}\ket{b_1\cdots b_n}\pm\frac{1}{\sqrt{2}}\ket{\overline{b_1}\cdots\overline{b_n}} ，其中 bi‾=1−bi\overline{b_i}=1-b_i 。这是因为从左上角到右下角的对角线捕获标识，而从左下角到右上角的对角线捕获从 vv 到 N−vN-v (其中 N−vN-v 可以用倒置所有 vv 的位置算得) 的映射。
以下解决方案特别是有用：
  • 将矢量的条目与其他值交换
def solve[n:!ℕ](qs:𝔹^n){
  x:=0:𝔹;
  // swap x with LSB of qs
  // necessary because Silq would block `qs` in the body of `if qs[0] {...}`
  (x,qs[0]):=(qs[0],x);
  if x{ // flip all other bits if LSB=1
    for i in [1..n){
      qs[i]:=X(qs[i]);
    }
  }
  x:=H(x); // map LSB to 1/√̅2 (|0⟩±|1⟩)
  if x{
    // flip all other bits if LSB=1
    // - if LSB was originally 0, this flips the bits iff H flipped the LSB
    // - if LSB was originally 1, this leaves the other bits flipped
    //   if H flipped the LSB and restores the other bits otherwise
    for i in [1..n){
      qs[i]:=X(qs[i]);
    }
  }
  // swap x back
  (qs[0],x):=(x,qs[0]);
  forget(x=0);
  return qs;
}
// EXAMPLE CALL
def main(){
  // example usage for N=3
  x := 0:!int[3];
  y := x as 𝔹^3;
  return solve(y);
}
# 参考资料 [1]
  1. Silq - Examples ↩︎