QFT Circuit Explorer

Interactive tools for understanding QFT circuit structure and approximate truncation

1. QFT Circuit Gate Map

Visualize the two-qubit gate pattern of the \(n\)-qubit QFT. Each cell represents a controlled-\(R_k\) gate between two qubits. Drag the slider to change the number of qubits.

viewof nQubits = Inputs.range([2, 8], {
  value: 4,
  step: 1,
  label: "Number of qubits n"
})

{
  // Build the gate list for an n-qubit QFT
  const gates = [];
  for (let i = 0; i < nQubits; i++) {
    for (let j = i + 1; j < nQubits; j++) {
      const k = j - i + 1;
      gates.push({
        control: j,
        target: i,
        k: k,
        angle: 2 * Math.PI / Math.pow(2, k),
        label: `R${k}`
      });
    }
  }

  const data = gates.map(g => ({
    x: g.control,
    y: g.target,
    k: g.k,
    label: g.label,
    angle_deg: (360 / Math.pow(2, g.k)).toFixed(1)
  }));

  return Plot.plot({
    title: `${nQubits}-qubit QFT: ${gates.length} controlled rotation gates`,
    width: Math.max(400, nQubits * 60 + 100),
    height: Math.max(300, nQubits * 60 + 80),
    marginLeft: 60,
    marginBottom: 50,
    x: {
      label: "Control qubit",
      domain: d3.range(nQubits),
      tickFormat: d => `q${d}`
    },
    y: {
      label: "Target qubit",
      domain: d3.range(nQubits),
      tickFormat: d => `q${d}`
    },
    color: {
      scheme: "blues",
      domain: [1, nQubits],
      label: "Rotation index k",
      legend: true
    },
    marks: [
      Plot.cell(data, {
        x: "x",
        y: "y",
        fill: "k",
        tip: true,
        title: d => `CR${d.k}: q${d.x} → q${d.y}\nAngle: ${d.angle_deg}°`
      }),
      Plot.text(data, {
        x: "x",
        y: "y",
        text: "label",
        fill: "white",
        fontSize: 11,
        fontWeight: "bold"
      })
    ]
  });
}

html`<div style="
  background: #f0f4ff;
  border-left: 4px solid #3b82f6;
  padding: 12px 18px;
  border-radius: 6px;
  margin: 10px 0;
  font-size: 15px;
">
  <strong>Gate count:</strong>
  ${nQubits} qubits →
  <strong>${nQubits * (nQubits - 1) / 2}</strong> two-qubit gates,
  <strong>${nQubits}</strong> Hadamards,
  <strong>${Math.floor(nQubits / 2)}</strong> SWAP gates for bit reversal.
  <br>
  <strong>Connectivity:</strong> Every qubit pair interacts — this is the complete graph K<sub>${nQubits}</sub>.
</div>`

2. Approximate QFT Truncation

The approximate QFT drops controlled rotations \(CR_k\) with \(k\) above a cutoff \(m\). Smaller-angle rotations contribute less to the transform and can be safely removed.

viewof nApprox = Inputs.range([2, 8], {
  value: 6,
  step: 1,
  label: "Number of qubits n"
})

viewof mCutoff = Inputs.range([1, 10], {
  value: 3,
  step: 1,
  label: "Cutoff m (keep CR_k for k ≤ m)"
})

{
  const gates = [];
  let keptCount = 0;
  let droppedCount = 0;

  for (let i = 0; i < nApprox; i++) {
    for (let j = i + 1; j < nApprox; j++) {
      const k = j - i + 1;
      const kept = k <= mCutoff;
      if (kept) keptCount++; else droppedCount++;
      gates.push({
        control: j,
        target: i,
        k: k,
        kept: kept,
        status: kept ? "Kept" : "Dropped"
      });
    }
  }

  const totalGates = nApprox * (nApprox - 1) / 2;
  const errorBound = Math.PI * nApprox * nApprox / Math.pow(2, mCutoff + 1);

  return Plot.plot({
    title: `Approximate QFT: ${keptCount} kept, ${droppedCount} dropped (${(droppedCount / totalGates * 100).toFixed(0)}% reduction)`,
    width: Math.max(400, nApprox * 60 + 100),
    height: Math.max(300, nApprox * 60 + 80),
    marginLeft: 60,
    marginBottom: 50,
    x: {
      label: "Control qubit",
      domain: d3.range(nApprox),
      tickFormat: d => `q${d}`
    },
    y: {
      label: "Target qubit",
      domain: d3.range(nApprox),
      tickFormat: d => `q${d}`
    },
    color: {
      domain: ["Kept", "Dropped"],
      range: ["#3b82f6", "#fca5a5"]
    },
    marks: [
      Plot.cell(gates, {
        x: "control",
        y: "target",
        fill: "status",
        tip: true,
        title: d => `CR${d.k}: ${d.status}\nAngle: ${(360 / Math.pow(2, d.k)).toFixed(2)}°`
      }),
      Plot.text(gates, {
        x: "control",
        y: "target",
        text: d => `R${d.k}`,
        fill: d => d.kept ? "white" : "#991b1b",
        fontSize: 11,
        fontWeight: "bold"
      })
    ]
  });
}

{
  const totalGates = nApprox * (nApprox - 1) / 2;
  let keptGates = 0;
  for (let i = 0; i < nApprox; i++) {
    for (let j = i + 1; j < nApprox; j++) {
      if (j - i + 1 <= mCutoff) keptGates++;
    }
  }
  const errorBound = Math.PI * nApprox * nApprox / Math.pow(2, mCutoff + 1);

  return html`<div style="
    background: ${errorBound < 0.1 ? '#f0fdf4' : errorBound < 1 ? '#fffbeb' : '#fef2f2'};
    border-left: 4px solid ${errorBound < 0.1 ? '#22c55e' : errorBound < 1 ? '#f59e0b' : '#ef4444'};
    padding: 12px 18px;
    border-radius: 6px;
    margin: 10px 0;
    font-size: 15px;
  ">
    <strong>Approximation error bound:</strong>
    ‖QFT − QFT̃‖ ≤ πn²/2<sup>m+1</sup>
    = π·${nApprox}²/2<sup>${mCutoff + 1}</sup>
    = <span style="font-weight: bold; color: ${errorBound < 0.1 ? '#16a34a' : errorBound < 1 ? '#d97706' : '#dc2626'}">
      ${errorBound.toFixed(4)}
    </span>
    ${errorBound < 0.01 ? ' ✓ Excellent' : errorBound < 0.1 ? ' ✓ Good' : errorBound < 1 ? ' ⚠ Marginal' : ' ✗ Too large'}
    <br>
    <strong>Gates:</strong> ${keptGates} kept out of ${totalGates}
    (${((totalGates - keptGates) / totalGates * 100).toFixed(0)}% reduction)
  </div>`;
}

3. Gate Count Scaling

Compare exact vs approximate QFT gate counts as the number of qubits grows.

viewof mScaling = Inputs.range([2, 20], {
  value: 6,
  step: 1,
  label: "Cutoff m for approximate QFT"
})

{
  const data = [];
  for (let n = 2; n <= 32; n++) {
    const exact = n * (n - 1) / 2;
    let approx = 0;
    for (let i = 0; i < n; i++) {
      approx += Math.min(n - i - 1, mScaling);
    }
    data.push({ n, count: exact, type: "Exact QFT" });
    data.push({ n, count: approx, type: `Approximate (m=${mScaling})` });
  }

  return Plot.plot({
    title: "Two-qubit gate count: Exact vs Approximate QFT",
    width,
    height: 380,
    marginLeft: 60,
    x: { label: "Number of qubits n", domain: [2, 32] },
    y: { label: "Two-qubit gates", type: "log", domain: [1, 600] },
    color: {
      domain: ["Exact QFT", `Approximate (m=${mScaling})`],
      range: ["#ef4444", "#3b82f6"]
    },
    marks: [
      Plot.line(data, {
        x: "n",
        y: "count",
        stroke: "type",
        strokeWidth: 2.5
      }),
      Plot.dot(data, {
        x: "n",
        y: "count",
        fill: "type",
        r: 3,
        tip: true,
        title: d => `n=${d.n}: ${d.count} gates (${d.type})`
      }),
      Plot.ruleY([1])
    ]
  });
}

html`<div style="
  background: #f8fafc;
  border-left: 4px solid #64748b;
  padding: 12px 18px;
  border-radius: 6px;
  margin: 10px 0;
  font-size: 14px;
  color: #475569;
">
  <strong>Scaling:</strong>
  Exact QFT grows as O(n²) = n(n−1)/2.
  Approximate QFT with cutoff m grows as O(n·m) ≈ O(n log n) when m = O(log n).
  <br>
  At n = 32 with m = ${mScaling}: exact = ${32 * 31 / 2} gates,
  approximate ≈ ${(() => { let s = 0; for (let i = 0; i < 32; i++) s += Math.min(31 - i, mScaling); return s; })()} gates
  (${(100 - 100 * (() => { let s = 0; for (let i = 0; i < 32; i++) s += Math.min(31 - i, mScaling); return s; })() / (32 * 31 / 2)).toFixed(0)}% reduction).
</div>`