class Qubit {
  private state: Complex[];

  constructor(alpha: Complex = new Complex(1, 0), beta: Complex = new Complex(0, 0)) {
    this.state = [alpha, beta];
    this.normalize();
  }

  private normalize(): void {
    const norm = Math.sqrt(this.state[0].magnitude() ** 2 + this.state[1].magnitude() ** 2);
    this.state[0] = this.state[0].divide(norm);
    this.state[1] = this.state[1].divide(norm);
  }

  measure(): number {
    const prob0 = this.state[0].magnitude() ** 2;
    return Math.random() < prob0 ? 0 : 1;
  }

  getState(): Complex[] {
    return [...this.state];
  }

  applyGate(gate: Complex[][]): void {
    const newState: Complex[] = [gate[0][0].multiply(this.state[0]).add(gate[0][1].multiply(this.state[1])), gate[1][0].multiply(this.state[0]).add(gate[1][1].multiply(this.state[1]))];
    this.state = newState;
  }
}

class Complex {
  real: number;
  imag: number;

  constructor(real: number, 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);
  }

  divide(scalar: number): Complex {
    return new Complex(this.real / scalar, this.imag / scalar);
  }

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

class QuantumGates {
  static pauliX(): Complex[][] {
    return [
      [new Complex(0, 0), new Complex(1, 0)],
      [new Complex(1, 0), new Complex(0, 0)],
    ];
  }

  static pauliY(): Complex[][] {
    return [
      [new Complex(0, 0), new Complex(0, -1)],
      [new Complex(0, 1), new Complex(0, 0)],
    ];
  }

  static pauliZ(): Complex[][] {
    return [
      [new Complex(1, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(-1, 0)],
    ];
  }

  static hadamard(): Complex[][] {
    const sqrt2 = Math.sqrt(2);
    return [
      [new Complex(1 / sqrt2, 0), new Complex(1 / sqrt2, 0)],
      [new Complex(1 / sqrt2, 0), new Complex(-1 / sqrt2, 0)],
    ];
  }

  static phase(phi: number): Complex[][] {
    return [
      [new Complex(1, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(Math.cos(phi), Math.sin(phi))],
    ];
  }

  static cnot(): Complex[][] {
    // 简化版，实际需要 4x4 矩阵
    return [
      [new Complex(1, 0), new Complex(0, 0), new Complex(0, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(1, 0), new Complex(0, 0), new Complex(0, 0)],
      [new Complex(0, 0), new Complex(0, 0), new Complex(0, 0), new Complex(1, 0)],
      [new Complex(0, 0), new Complex(0, 0), new Complex(1, 0), new Complex(0, 0)],
    ];
  }
}

class GroverSearch {
  private n: number;
  private markedItem: number;

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

  search(): number {
    const iterations = Math.floor((Math.PI * Math.sqrt(2 ** this.n)) / 4);

    // 初始化均匀叠加态
    const state = new Array(2 ** this.n).fill(0);
    for (let i = 0; i < state.length; i += 1) {
      state[i] = 1 / Math.sqrt(2 ** this.n);
    }

    for (let iter = 0; iter < iterations; iter += 1) {
      // 应用 oracle
      this.applyOracle(state);

      // 应用扩散算子
      this.applyDiffusion(state);
    }

    // 测量
    return this.measure(state);
  }

  private applyOracle(state: number[]): void {
    state[this.markedItem] = -state[this.markedItem];
  }

  private applyDiffusion(state: number[]): void {
    const mean = state.reduce((sum, amp) => sum + amp, 0) / state.length;

    for (let i = 0; i < state.length; i += 1) {
      state[i] = 2 * mean - state[i];
    }
  }

  private measure(state: number[]): number {
    const probabilities = state.map((amp) => amp ** 2);
    const random = Math.random();
    let cumulative = 0;

    for (let i = 0; i < probabilities.length; i += 1) {
      cumulative += probabilities[i];
      if (random <= cumulative) {
        return i;
      }
    }

    return 0;
  }
}

function quantumFourierTransform(state: Complex[]): Complex[] {
  const n = Math.log2(state.length);
  const result: Complex[] = new Array(state.length).fill(new Complex(0, 0));

  for (let i = 0; i < state.length; i += 1) {
    for (let j = 0; j < state.length; j += 1) {
      const angle = (2 * Math.PI * i * j) / state.length;
      const phase = new Complex(Math.cos(angle), Math.sin(angle));
      result[i] = result[i].add(state[j].multiply(phase));
    }
    result[i] = result[i].divide(Math.sqrt(state.length));
  }

  return result;
}

function shorFactorization(n: number): number[] {
  if (n % 2 === 0) return [2, n / 2];

  // 随机选择 a
  let a = Math.floor(Math.random() * (n - 2)) + 2;

  // 计算 gcd(a, n)
  let gcd = this.gcd(a, n);
  if (gcd > 1) return [gcd, n / gcd];

  // 量子部分：找到周期 r
  const r = this.findPeriod(a, n);

  if (r % 2 === 1) return this.shorFactorization(n); // 重新开始

  const factor1 = this.gcd(a ** (r / 2) - 1, n);
  const factor2 = this.gcd(a ** (r / 2) + 1, n);

  if (factor1 === 1 || factor2 === 1) return this.shorFactorization(n);

  return [factor1, factor2];
}

function findPeriod(a: number, n: number): number {
  // 简化版：暴力搜索周期
  let x = 1;
  for (let r = 1; r < n; r += 1) {
    x = (x * a) % n;
    if (x === 1) return r;
  }
  return n;
}

function gcd(a: number, b: number): number {
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}