// 复数类
class Complex {
  real: number;
  imag: number;

  constructor(real: number = 0, imag: number = 0) {
    this.real = real;
    this.imag = imag;
  }

  add(other: Complex): Complex {
    return new Complex(this.real + other.real, this.imag + other.imag);
  }

  multiply(other: Complex): Complex {
    return new Complex(this.real * other.real - this.imag * other.imag, this.real * other.imag + this.imag * other.real);
  }

  magnitude(): number {
    return Math.sqrt(this.real * this.real + this.imag * this.imag);
  }

  conjugate(): Complex {
    return new Complex(this.real, -this.imag);
  }

  toString(): string {
    if (this.imag === 0) return this.real.toString();
    if (this.real === 0) return this.imag === 1 ? 'i' : this.imag === -1 ? '-i' : this.imag + 'i';
    return `${this.real}${this.imag >= 0 ? '+' : ''}${this.imag}i`;
  }
}

// 量子比特
class Qubit {
  private state: Complex[];

  constructor(alpha: Complex = new Complex(1, 0), beta: Complex = new Complex(0, 0)) {
    // 归一化状态
    const norm = Math.sqrt(alpha.magnitude() ** 2 + beta.magnitude() ** 2);
    this.state = [new Complex(alpha.real / norm, alpha.imag / norm), new Complex(beta.real / norm, beta.imag / norm)];
  }

  // 获取状态向量
  getState(): Complex[] {
    return [...this.state];
  }

  // 测量量子比特 (返回0或1)
  measure(): number {
    const prob0 = this.state[0].magnitude() ** 2;
    return Math.random() < prob0 ? 0 : 1;
  }

  // 获取测量概率
  getProbabilities(): { prob0: number; prob1: number } {
    const prob0 = this.state[0].magnitude() ** 2;
    const prob1 = this.state[1].magnitude() ** 2;
    return { prob0, prob1 };
  }

  toString(): string {
    return `${this.state[0].toString()}|0⟩ + ${this.state[1].toString()}|1⟩`;
  }
}

// 量子门
class QuantumGate {
  private matrix: Complex[][];

  constructor(matrix: Complex[][]) {
    this.matrix = matrix;
  }

  // 应用量子门到量子比特
  apply(qubit: Qubit): Qubit {
    const state = qubit.getState();
    const newState: Complex[] = [new Complex(0, 0), new Complex(0, 0)];

    for (let i = 0; i < 2; i++) {
      for (let j = 0; j < 2; j++) {
        newState[i] = newState[i].add(this.matrix[i][j].multiply(state[j]));
      }
    }

    return new Qubit(newState[0], newState[1]);
  }

  // 获取矩阵
  getMatrix(): Complex[][] {
    return this.matrix.map((row) => [...row]);
  }

  // 泡利-X门 (NOT门)
  static X(): QuantumGate {
    return new QuantumGate([
      [new Complex(0, 0), new Complex(1, 0)],
      [new Complex(1, 0), new Complex(0, 0)],
    ]);
  }

  // 泡利-Y门
  static Y(): QuantumGate {
    return new QuantumGate([
      [new Complex(0, 0), new Complex(0, -1)],
      [new Complex(0, 1), new Complex(0, 0)],
    ]);
  }

  // 泡利-Z门
  static Z(): QuantumGate {
    return new QuantumGate([
      [new Complex(1, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(-1, 0)],
    ]);
  }

  // 阿达马门 (Hadamard门)
  static H(): QuantumGate {
    const sqrt2 = Math.sqrt(2) / 2;
    return new QuantumGate([
      [new Complex(sqrt2, 0), new Complex(sqrt2, 0)],
      [new Complex(sqrt2, 0), new Complex(-sqrt2, 0)],
    ]);
  }

  // 相位门
  static S(): QuantumGate {
    return new QuantumGate([
      [new Complex(1, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(0, 1)],
    ]);
  }

  // T门 (π/8门)
  static T(): QuantumGate {
    const cosPi8 = Math.cos(Math.PI / 8);
    const sinPi8 = Math.sin(Math.PI / 8);
    return new QuantumGate([
      [new Complex(1, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(cosPi8, sinPi8)],
    ]);
  }

  // 旋转门
  static RX(theta: number): QuantumGate {
    const cos = Math.cos(theta / 2);
    const sin = Math.sin(theta / 2);
    return new QuantumGate([
      [new Complex(cos, 0), new Complex(0, -sin)],
      [new Complex(0, -sin), new Complex(cos, 0)],
    ]);
  }

  static RY(theta: number): QuantumGate {
    const cos = Math.cos(theta / 2);
    const sin = Math.sin(theta / 2);
    return new QuantumGate([
      [new Complex(cos, 0), new Complex(-sin, 0)],
      [new Complex(sin, 0), new Complex(cos, 0)],
    ]);
  }

  static RZ(theta: number): QuantumGate {
    const cos = Math.cos(theta / 2);
    const sin = Math.sin(theta / 2);
    return new QuantumGate([
      [new Complex(cos, -sin), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(cos, sin)],
    ]);
  }
}

// 使用示例
function quantumGatesExample() {
  // 创建|0⟩状态的量子比特
  let qubit = new Qubit();

  console.log('Initial state:', qubit.toString());
  console.log('Probabilities:', qubit.getProbabilities());

  // 应用阿达马门
  qubit = QuantumGate.H().apply(qubit);
  console.log('After H gate:', qubit.toString());
  console.log('Probabilities:', qubit.getProbabilities());

  // 应用Z门
  qubit = QuantumGate.Z().apply(qubit);
  console.log('After Z gate:', qubit.toString());
  console.log('Probabilities:', qubit.getProbabilities());

  // 测量
  const measurements: number[] = [];
  for (let i = 0; i < 1000; i++) {
    measurements.push(qubit.measure());
  }
  const prob0 = measurements.filter((m) => m === 0).length / measurements.length;
  const prob1 = measurements.filter((m) => m === 1).length / measurements.length;

  console.log('Measurement results (1000 samples):');
  console.log('P(0):', prob0, 'P(1):', prob1);
}

class QuantumFourierTransform {
  // 量子傅里叶变换
  static QFT(qubits: Qubit[]): Qubit[] {
    const n = qubits.length;
    const result: Qubit[] = [...qubits];

    for (let i = 0; i < n; i++) {
      // 应用阿达马门
      result[i] = QuantumGate.H().apply(result[i]);

      // 应用受控旋转门
      for (let j = i + 1; j < n; j++) {
        const angle = Math.PI / 2 ** (j - i);
        // 应用受控相位旋转
        result[i] = this.applyControlledPhase(result[i], result[j], angle);
      }
    }

    // 反转量子比特顺序
    return result.reverse();
  }

  // 逆量子傅里叶变换
  static IQFT(qubits: Qubit[]): Qubit[] {
    const n = qubits.length;
    let result: Qubit[] = [...qubits];

    // 反转顺序
    result = result.reverse();

    for (let i = 0; i < n; i++) {
      // 应用受控旋转门 (逆序)
      for (let j = i - 1; j >= 0; j--) {
        const angle = -Math.PI / 2 ** (i - j);
        result[i] = this.applyControlledPhase(result[i], result[j], angle);
      }

      // 应用阿达马门
      result[i] = QuantumGate.H().apply(result[i]);
    }

    return result;
  }

  // 应用受控相位旋转
  private static applyControlledPhase(target: Qubit, control: Qubit, angle: number): Qubit {
    // 简化的实现 - 在实际量子计算机中，这需要多量子比特门
    // 这里我们只对目标量子比特应用相位旋转，如果控制量子比特是|1⟩
    const controlProbs = control.getProbabilities();

    if (controlProbs.prob1 > 0.5) {
      // 如果控制量子比特更可能是|1⟩
      return QuantumGate.RZ(angle).apply(target);
    }

    return target;
  }

  // 离散傅里叶变换 (经典实现，用于比较)
  static DFT(signal: Complex[]): Complex[] {
    const N = signal.length;
    const result: Complex[] = [];

    for (let k = 0; k < N; k++) {
      let sum = new Complex(0, 0);
      for (let n = 0; n < N; n++) {
        const angle = (-2 * Math.PI * k * n) / N;
        const twiddle = new Complex(Math.cos(angle), Math.sin(angle));
        sum = sum.add(signal[n].multiply(twiddle));
      }
      result.push(sum);
    }

    return result;
  }

  // 逆离散傅里叶变换
  static IDFT(signal: Complex[]): Complex[] {
    const N = signal.length;
    const result: Complex[] = [];

    for (let n = 0; n < N; n++) {
      let sum = new Complex(0, 0);
      for (let k = 0; k < N; k++) {
        const angle = (2 * Math.PI * k * n) / N;
        const twiddle = new Complex(Math.cos(angle), Math.sin(angle));
        sum = sum.add(signal[k].multiply(twiddle));
      }
      result.push(sum.multiply(new Complex(1 / N, 0)));
    }

    return result;
  }

  // 将整数编码为量子状态
  static encodeNumber(num: number, nQubits: number): Qubit[] {
    const qubits: Qubit[] = [];

    for (let i = 0; i < nQubits; i++) {
      const bit = (num >> i) & 1;
      if (bit === 1) {
        qubits.push(new Qubit(new Complex(0, 0), new Complex(1, 0))); // |1⟩
      } else {
        qubits.push(new Qubit(new Complex(1, 0), new Complex(0, 0))); // |0⟩
      }
    }

    return qubits;
  }

  // 从量子状态解码整数
  static decodeNumber(qubits: Qubit[]): number {
    let result = 0;

    for (let i = 0; i < qubits.length; i++) {
      const measurement = qubits[i].measure();
      if (measurement === 1) {
        result |= 1 << i;
      }
    }

    return result;
  }
}

// 使用示例
function qftExample() {
  console.log('Quantum Fourier Transform Example');

  // 创建4个量子比特表示数字5 (二进制: 0101)
  const qubits = QuantumFourierTransform.encodeNumber(5, 4);
  console.log('Original qubits:');
  qubits.forEach((q, i) => console.log(`Qubit ${i}:`, q.toString()));

  // 应用QFT
  const transformed = QuantumFourierTransform.QFT(qubits);
  console.log('\nAfter QFT:');
  transformed.forEach((q, i) => console.log(`Qubit ${i}:`, q.toString()));

  // 应用逆QFT
  const restored = QuantumFourierTransform.IQFT(transformed);
  console.log('\nAfter IQFT:');
  restored.forEach((q, i) => console.log(`Qubit ${i}:`, q.toString()));

  // 多次测量验证
  const measurements: number[] = [];
  for (let i = 0; i < 100; i++) {
    measurements.push(QuantumFourierTransform.decodeNumber(restored));
  }

  console.log('\nMeasurement results (should be close to 5):');
  const avg = measurements.reduce((a, b) => a + b, 0) / measurements.length;
  console.log('Average:', avg);
}

class GroverSearch {
  private n: number; // 搜索空间大小 (2^n 个元素)
  private target: number; // 目标元素
  private qubits: Qubit[];

  constructor(n: number, target: number) {
    this.n = n;
    this.target = target;
    this.qubits = this.initializeQubits();
  }

  // 初始化量子比特为均匀叠加态
  private initializeQubits(): Qubit[] {
    const qubits: Qubit[] = [];

    for (let i = 0; i < this.n; i++) {
      // 创建|0⟩状态
      const qubit = new Qubit();
      // 应用阿达马门创建均匀叠加
      qubits.push(QuantumGate.H().apply(qubit));
    }

    return qubits;
  }

  // 搜索算法
  search(maxIterations?: number): number {
    const optimalIterations = Math.floor((Math.PI * Math.sqrt(2 ** this.n)) / 4);
    const iterations = maxIterations || optimalIterations;

    console.log(`Searching for ${this.target} in space of size ${2 ** this.n}`);
    console.log(`Optimal iterations: ${optimalIterations}, using: ${iterations}`);

    for (let i = 0; i < iterations; i++) {
      this.applyOracle();
      this.applyDiffusionOperator();
    }

    // 测量结果
    return this.measure();
  }

  // 应用Oracle (标记目标状态)
  private applyOracle(): void {
    // 在经典模拟中，我们需要检查每个可能的状态
    // 在实际量子计算机中，这是一个量子Oracle

    // 对于目标状态，应用Z门 (相位翻转)
    // 这里简化为直接修改量子状态的相位

    // 注意：这是一个简化的实现
    // 实际的Oracle应该是一个量子电路

    // 对于我们的目标，我们假设可以直接访问量子状态
    // 在实际实现中，这需要更复杂的量子电路
    this.applyPhaseFlip(this.target);
  }

  // 应用相位翻转到目标状态
  private applyPhaseFlip(targetIndex: number): void {
    // 这是一个简化的实现
    // 在实际量子计算机中，相位翻转是通过量子门实现的

    // 对于多量子比特系统，我们需要应用受控Z门
    // 这里我们直接修改状态向量 (仅用于模拟)

    // 注意：这不是真正的量子实现，只是经典模拟
    console.log(`Applying phase flip to state |${targetIndex.toString(2).padStart(this.n, '0')}⟩`);
  }

  // 应用扩散算子 (Diffusion Operator)
  private applyDiffusionOperator(): void {
    // 扩散算子 = H^{\otimes n} (2|s⟩⟨s| - I) H^{\otimes n}
    // 其中 |s⟩ 是均匀叠加态

    // 步骤1: 应用阿达马门到所有量子比特
    for (let i = 0; i < this.n; i++) {
      this.qubits[i] = QuantumGate.H().apply(this.qubits[i]);
    }

    // 步骤2: 应用相位翻转到 |0...0⟩ 状态
    this.applyPhaseFlip(0);

    // 步骤3: 再次应用阿达马门
    for (let i = 0; i < this.n; i++) {
      this.qubits[i] = QuantumGate.H().apply(this.qubits[i]);
    }
  }

  // 测量量子寄存器
  private measure(): number {
    let result = 0;

    for (let i = 0; i < this.n; i++) {
      const measurement = this.qubits[i].measure();
      if (measurement === 1) {
        result |= 1 << i;
      }
    }

    return result;
  }

  // 获取当前状态的概率分布
  getProbabilityDistribution(): Map<number, number> {
    const distribution = new Map<number, number>();

    // 对于经典模拟，我们使用蒙特卡洛方法估计概率
    const samples = 10000;
    for (let i = 0; i < samples; i++) {
      const measurement = this.measure();
      distribution.set(measurement, (distribution.get(measurement) || 0) + 1);
    }

    // 归一化
    for (const [key, value] of distribution) {
      distribution.set(key, value / samples);
    }

    return distribution;
  }

  // 重置搜索
  reset(): void {
    this.qubits = this.initializeQubits();
  }
}

// 简化的Grover搜索实现 (使用经典模拟)
class SimplifiedGroverSearch {
  private n: number;
  private target: number;

  constructor(n: number, target: number) {
    this.n = n;
    this.target = target;
  }

  // 模拟Grover搜索
  search(): { result: number; iterations: number; success: boolean } {
    const searchSpace = 2 ** this.n;
    const optimalIterations = Math.floor((Math.PI * Math.sqrt(searchSpace)) / 4);

    console.log(`Simplified Grover Search for ${this.target} in ${searchSpace} elements`);

    // 模拟量子搜索的概率放大
    let probability = 1 / searchSpace; // 初始均匀分布

    for (let iteration = 0; iteration < optimalIterations; iteration++) {
      // Oracle: 如果是目标状态，概率翻倍
      if (Math.random() < probability) {
        probability *= 2;
      }

      // 扩散算子: 放大正确状态的概率
      probability = Math.sin((2 * iteration + 1) * Math.asin(Math.sqrt(probability))) ** 2;
    }

    // 模拟测量
    const random = Math.random();
    const found = random < probability;

    return {
      result: found ? this.target : Math.floor(Math.random() * searchSpace),
      iterations: optimalIterations,
      success: found,
    };
  }

  // 经典搜索 (用于比较)
  classicalSearch(): { result: number; iterations: number } {
    const searchSpace = 2 ** this.n;
    let iterations = 0;

    for (let i = 0; i < searchSpace; i++) {
      iterations++;
      if (i === this.target) {
        return { result: i, iterations };
      }
    }

    return { result: -1, iterations };
  }
}

// 使用示例
function groverExample() {
  console.log("Grover's Algorithm Example");

  // 搜索4位空间中的目标 (16个可能值)
  const n = 4;
  const target = 7; // 二进制: 0111

  const grover = new SimplifiedGroverSearch(n, target);
  const classical = grover.classicalSearch();

  console.log('\nClassical search:');
  console.log(`Found ${classical.result} in ${classical.iterations} iterations`);

  console.log('\nQuantum search (simplified):');
  const quantumResult = grover.search();
  console.log(`Found ${quantumResult.result}, success: ${quantumResult.success}, iterations: ${quantumResult.iterations}`);

  console.log(`\nSpeedup: ${classical.iterations / quantumResult.iterations}x`);
}

class ShorAlgorithm {
  // 简化的Shor算法实现 (只包含关键概念)
  private N: number; // 要分解的数

  constructor(N: number) {
    this.N = N;
  }

  // 经典部分: 寻找周期
  findPeriod(a: number): number {
    // 使用经典算法寻找 a^x mod N 的周期
    const seen = new Map<number, number>();
    let x = 0;
    let value = 1;

    while (!seen.has(value)) {
      seen.set(value, x);
      value = (value * a) % this.N;
      x++;

      // 如果回到1，找到了周期
      if (value === 1) {
        return x;
      }

      // 防止无限循环
      if (x > this.N) {
        return -1; // 没有找到周期
      }
    }

    return -1;
  }

  // 量子部分模拟: 量子周期寻找
  quantumPeriodFinding(a: number): number {
    // 这是一个简化的模拟
    // 实际的Shor算法需要量子傅里叶变换

    console.log(`Finding period of ${a}^x mod ${this.N}`);

    // 模拟量子计算
    const period = this.findPeriod(a);

    if (period !== -1) {
      console.log(`Found period: ${period}`);
      return period;
    } else {
      console.log('No period found');
      return -1;
    }
  }

  // 因数分解
  factorize(): { factors: number[]; success: boolean } {
    // 步骤1: 选择随机数a < N
    const a = Math.floor(Math.random() * (this.N - 2)) + 2;

    console.log(`\nFactoring ${this.N} with a = ${a}`);

    // 步骤2: 计算gcd(a, N)
    const gcd = this.greatestCommonDivisor(a, this.N);
    if (gcd !== 1) {
      console.log(`Found factor: ${gcd}`);
      return { factors: [gcd, this.N / gcd], success: true };
    }

    // 步骤3: 使用量子算法寻找周期
    const r = this.quantumPeriodFinding(a);
    if (r === -1 || r % 2 !== 0) {
      console.log('Failed to find even period');
      return { factors: [], success: false };
    }

    // 步骤4: 计算可能的因子
    const factor1 = this.greatestCommonDivisor(Math.pow(a, r / 2) - 1, this.N);
    const factor2 = this.greatestCommonDivisor(Math.pow(a, r / 2) + 1, this.N);

    if (factor1 > 1 && factor1 < this.N && factor2 > 1 && factor2 < this.N) {
      console.log(`Found factors: ${factor1}, ${factor2}`);
      return { factors: [factor1, factor2], success: true };
    }

    return { factors: [], success: false };
  }

  // 欧几里得算法计算最大公约数
  private greatestCommonDivisor(a: number, b: number): number {
    while (b !== 0) {
      const temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

  // 检查是否为质数 (简单实现)
  private isPrime(n: number): boolean {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;

    for (let i = 5; i * i <= n; i += 6) {
      if (n % i === 0 || n % (i + 2) === 0) return false;
    }

    return true;
  }

  // 尝试因数分解 (多次尝试)
  factorizeWithRetries(maxRetries: number = 10): { factors: number[]; success: boolean } {
    // 首先检查是否为质数
    if (this.isPrime(this.N)) {
      return { factors: [this.N], success: true };
    }

    for (let attempt = 0; attempt < maxRetries; attempt++) {
      const result = this.factorize();
      if (result.success) {
        return result;
      }
    }

    return { factors: [], success: false };
  }
}

// 使用示例
function shorExample() {
  console.log("Shor's Algorithm Example (Simplified)");

  const shor = new ShorAlgorithm(15); // 15 = 3 * 5
  const result = shor.factorizeWithRetries();

  console.log('\nFinal result:');
  if (result.success) {
    console.log(`Successfully factored: ${result.factors.join(' * ')}`);
  } else {
    console.log('Failed to factor the number');
  }
}