Shor算法的实现与解析

### Shor算法的实现与解析 #### 1. 引言 Shor算法是量子计算领域的一个重要算法，主要用于整数分解。本文将使用Cirq库详细介绍Shor算法的实现过程，包括经典的阶查找和量子的阶查找，以及如何利用这些方法完成完整的因式分解。 #### 2. 经典阶查找 经典阶查找是通过计算序列 \(a^2 \bmod n, a^3 \bmod n, a^4 \bmod n, \cdots\) ，直到找到一个整数 \(r\) ，使得 \(a^r \equiv 1 \pmod{n}\) 。以下是实现该功能的Python代码： ```python import fractions import math import random import numpy as np import sympy from typing import Callable, List, Optional, Sequence, Union import cirq def classical_order_finder(a: int, n: int) -> Optional[int]: """Computes smallest positive r such that a**r mod n == 1.""" # Make sure a is both valid and in Z/nZ if a < 2 or a >= n or math.gcd(a, n) > 1: raise ValueError(f"Invalid a={a} for modulus n={n}.") # Determine the order r, x = 1, a while x != 1: x = (a**r) % n r += 1 return r n = 15 a = 8 r = classical_order_finder(a, n) # Check that the order is indeed correct print(f"a^r mod n = {a}^{r} mod {n} = {a**r % n}") ``` 输出结果为： ```plaintext a^r mod n = 8^4 mod 15 = 1 ``` 这个算法的时间复杂度为 \(O(\varphi(n))\) ，大约为 \(O(2^{L/2})\) ，其中 \(L\) 是 \(n\) 的二进制位数，效率较低。 #### 3. 量子阶查找 量子计算部分是Shor算法的核心，主要通过量子相位估计来完成阶查找。具体来说，是使用一个酉算子 \(U\) 来计算模幂函数 \(f_a(z)\) 。 ##### 3.1 Cirq中的量子算术运算 首先，我们来看一个简单的量子算术运算示例——加法运算。以下是定义加法运算的代码： ```python class Adder(cirq.ArithmeticOperation): """Quantum addition.""" def __init__(self, target_register, input_register): self.input_register = input_register self.target_register = target_register def registers(self): return self.target_register, self.input_register def with_registers(self, *new_registers): return Adder(*new_registers) def apply(self, target_value, input_value): return target_value + input_value # Two qubit registers qreg1 = cirq.LineQubit.range(2) qreg2 = cirq.LineQubit.range(2, 4) # Define the circuit circ = cirq.Circuit( cirq.ops.X.on(qreg1[0]), cirq.ops.X.on(qreg2[1]), Adder(input_register=qreg1, target_register=qreg2), cirq.measure_each(*qreg1), cirq.measure_each(*qreg2) ) # Display it print("Circuit:\n") print(circ) # Print the measurement outcomes print("\n\nMeasurement outcomes:\n") print(cirq.sample(circ, repetitions=5).data) ``` 输出结果如下： ```plaintext Circuit: 0: ---X---#3------------------------------------------M--- | 1: -------#4------------------------------------------M--- | 2: -------<__main__.Adder object at 0x7fb5bb147be0>---M--- | 3: ---X---#2------------------------------------------M--- Measurement outcomes: 0 1 2 3 0 1 0 1 1 1 1 0 1 1 2 1 0 1 1 3 1 0 1 1 4 1 0 1 1 ``` 我们还可以查看加法运算的酉矩阵： ```python print(cirq.unitary( Adder(target_register=cirq.LineQubit.range(2), input_register=1) ).astype(np.int32)) ``` 输出结果为： ```plaintext array([[0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]], dtype=int32) ``` 这个酉矩阵的第 \(i\) 列表示状态 \(|i + 1 \bmod 4\rangle\) 。 ##### 3.2 模幂算术运算 模幂算术运算是Shor算法中非常重要的一部分。以下是定义模幂运算的代码： ```python class ModularExp(cirq.ArithmeticOperation): """Quantum modular exponentiation. This class represents the unitary which multiplies base raised to exponent into the target modulo the given modulus. More precisely, it represents the unitary V which computes modular exponentiation a**e mod n: V|y>|e> = |y * a**e mod n> |e> 0 <= y < n V|y>|e> = |y> |e> n <= y where y is the target register, e is the exponent register, a is the base and n is the modulus. Consequently, V|y>|e> = (U**e|r>)|e> where U is the unitary defined as U|y> = |y * a mod n> 0 <= y < n U|y> = |y> n <= y """ def __init__( self, target: Sequence[cirq.Qid], exponent: Union[int, Sequence[cirq.Qid]], base: int, modulus: int ) -> None: if len(target) < modulus.bit_length(): raise ValueError(f'Register with {len(target)} qubits is too small ' f'for modulus {modulus}') self.target = target self.exponent = exponent self.base = base self.modulus = modulus def registers(self) -> Sequence[Union[int, Sequence[cirq.Qid]]]: return self.target, self.exponent, self.base, self.modulus def with_registers( self, *new_registers: Union[int, Sequence['cirq.Qid']], ) -> cirq.ArithmeticOperation: if len(new_registers) != 4: raise ValueError(f'Expected 4 registers (target, exponent, base, ' f'modulus), but got {len(new_registers)}') target, exponent, base, modulus = new_registers if not isinstance(target, Sequence): raise ValueError( f'Target must be a qubit register, got {type(target)}') if not isinstance(base, int): raise ValueError( f'Base must be a classical constant, got {type(base)}') if not isinstance(modulus, int): raise ValueError( f'Modulus must be a classical constant, got {type(modulus)}') return ModularExp(target, exponent, base, modulus) def apply(self, *register_values: int) -> int: assert len(register_values) == 4 target, exponent, base, modulus = register_values if target >= modulus: return target return (target * base**exponent) % modulus def _circuit_diagram_info_( self, args: cirq.CircuitDiagramInfoArgs, ) -> cirq.CircuitDiagramInfo: assert args.known_qubits is not None wire_symbols: List[str] = [] t, e = 0, 0 for qubit in args.known_qubits: if qubit in self.target: if t == 0: if isinstance(self.exponent, Sequence): e_str = 'e' else: e_str = str(self.exponent) wire_symbols.append( f'ModularExp(t*{self.base}**{e_str} % {self.modulus})') else: wire_symbols.append('t' + str(t)) t += 1 if isinstance(self.exponent, Sequence) and qubit in self.exponent: wire_symbols.append('e' + str(e)) e += 1 return cirq.CircuitDiagramInfo(wire_symbols=tuple(wire_symbols)) ``` 以 \(n = 15\) 为例，我们可以计算分解该数所需的量子比特数： ```python n = 15 L = n.bit_length() # The target register has L qubits target = cirq.LineQubit.range(L) # The exponent register has 2L + 3 qubits exponent = cirq.LineQubit.range(L, 3 * L + 3) # Display the total number of qubits to factor this n print(f"To factor n = {n} which has L = {L} bits, we need 3L + 3 = {3 * L + 3} qubits.") ``` 输出结果为： ```plaintext To factor n = 15 which has L = 4 bits, we need 3L + 3 = 15 qubits. ``` ##### 3.3 在电路中使用模幂运算 Shor算法的量子部分是通过相位估计完成的，其中使用了我们定义的模幂运算。以下是创建阶查找量子电路的函数： ```python def make_order_finding_circuit(a: int, n: int) -> cirq.Circuit: """Returns quantum circuit which computes the order of a modulo n. The circuit uses Quantum Phase Estimation to compute an eigenvalue of the unitary U|y> = |y * a mod n> 0 <= y < n U|y> = |y> n <= y """ L = n.bit_length() target = cirq.LineQubit.range(L) exponent = cirq.LineQubit.range(L, 3 * L + 3) return cirq.Circuit( cirq.X(target[L - 1]), cirq.H.on_each(*exponent), ModularExp(target, exponent, a, n), cirq.QFT(*exponent, inverse=True), cirq.measure(*exponent, key='exponent'), ) n = 15 a = 7 circuit = make_order_finding_circuit(a, n) print(circuit) ``` 我们可以通过一个较小的电路来展示测量结果： ```python circuit = make_order_finding_circuit(a=5, n=6) res = cirq.sample(circuit, repetitions=8) print("Raw measurements:") print(res) print ```