Quantum circuit

Prompt

Create a visualization of the quantum circuit needed for Shors algorithm. Use 5 Qbits and ket notation.

Of course! Visualizing Shor's algorithm is a great way to understand its structure.

Let's break it down. Shor's algorithm is used to find the prime factors of a large number, `N`. The quantum part of the algorithm is a "period-finding machine." We will create a circuit to factor the canonical example: **N = 15**.

### A Note on the 5-Qubit Constraint

You asked for 5 qubits. A *minimal, functional* circuit to factor N=15 actually requires **7 qubits**:
*   **Working Register:** To store numbers up to N-1 (i.e., 14), we need 4 qubits ($2^4 = 16$). Let's call this `n = 4`.
*   **Counting Register:** For a high probability of success, this register should have `2n = 8` qubits. However, we can construct a minimal example with just **3 qubits** ($2^3=8$).

Using only 5 qubits is insufficient for a real demonstration of factoring N=15. However, we can create a **conceptual visualization using 5 qubits (2 for counting, 3 for working)** to show the *structure* of the algorithm, and then explain the full 7-qubit process with ket notation.

Let's proceed with the **correct 7-qubit version** for clarity, as it allows us to follow the real computational steps.

---

### The Goal: Factoring N=15

1.  **Classical Part:**
    *   Pick a random number `a` that is coprime to N. Let's pick **`a = 7`**.
    *   (Check: `gcd(7, 15) = 1`. We're good.)
2.  **Quantum Part (The Circuit):**
    *   Find the period `r` of the function `f(x) = a^x mod N`.
    *   This means finding the smallest `r > 0` such that `7^r ≡ 1 (mod 15)`.
    *   The period is `r=4` because:
        *   $7^1 \mod 15 = 7$
        *   $7^2 \mod 15 = 49 \mod 15 = 4$
        *   $7^3 \mod 15 = 343 \mod 15 = 13$
        *   $7^4 \mod 15 = 2401 \mod 15 = 1$
3.  **Classical Part (Post-Processing):**
    *   Use `r` to find the factors of N.

---
### Visualization of the Quantum Circuit (for N=15, a=7)

Here is the circuit structure. We will use 3 qubits for the counting register and 4 for the working register.

**Register Setup:**
*   **Counting Register (q₀, q₁, q₂):** Starts as `|000⟩`. Will be used to find the period.
*   **Working Register (q₃, q₄, q₅, q₆):** Starts as `|0001⟩` (representing the number 1). This is where the `mod 15` calculation happens.

```
          ┌───┐                                     ┌───────┐┌─┐
q₀:|0⟩────┤ H ├───────■─────────────────────────────┤       ├┤M├
          ├───┤       │                             │       │└╥┘
q₁:|0⟩────┤ H ├───────■─────────────────────────────┤ QFT⁻¹ ├─╫─
          ├───┤       │                             │       │ ║
q₂:|0⟩────┤ H ├───────■─────────────────────────────┤       ├─╫─
          └───┘     ┌─┴─┐   ┌───┐   ┌───┐   ┌───┐   └───────┘ ║
q₃:|0⟩──────────────┤   ├───┤   ├───┤   ├───┤   ├──────────────╫─
q₄:|0⟩──────────────┤   ├───┤   ├───┤   ├───┤   ├──────────────╫─
q₅:|0⟩──────────────┤ U ├───┤ U ├───┤ U ├───┤ U ├──────────────╫─
q₆:|1⟩──────────────┤   ├───┤   ├───┤   ├───┤   ├──────────────╫─
                    └─┬─┘   └───┘   └───┘   └───┘              ║
                      │                                      ║
Control:            (q₀)    (q₁)    (q₂)                     ║
                                                             ║
Output:                                                   Classical Bits (c₁, c₂, c₃)
```

**What the gates mean:**
*   `H`: Hadamard gate.
*   `QFT⁻¹`: Inverse Quantum Fourier Transform.
*   `M`: Measurement.
*   **`C-U` (the big controlled gate):** This is the heart of the algorithm. It's the **Controlled-U** gate for modular exponentiation.
    *   It performs the operation: `|x⟩|y⟩ → |x⟩|a^x * y mod N⟩`.
    *   In our circuit, it's decomposed into controlled operations based on the qubits in the counting register. The first `C-U` is controlled by `q₂`, so it calculates `a^(2^0) = a^1`. The second is controlled by `q₁`, calculating `a^(2^1) = a^2`, and so on.

---

### Step-by-Step Evolution of the Quantum State (using Ket Notation)

Let's trace the state of our 7 qubits, `|ψ⟩`, through the circuit.

**1. Initialization (`|ψ₀⟩`)**

The system starts with the counting register in the state `|000⟩` and the working register in `|0001⟩` (which represents the integer 1).

`|ψ₀⟩ = |000⟩ ⊗ |0001⟩`
(This is `|0⟩` in the counting register and `|1⟩` in the working register.)

**2. Hadamard Gates (`|ψ₁⟩`)**

We apply Hadamard gates to each qubit in the counting register. This creates a uniform superposition of all possible values from 0 to 7.

`|ψ₁⟩ = (H⊗H⊗H)|000⟩ ⊗ |0001⟩`
`|ψ₁⟩ = (1/√8)(|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩) ⊗ |0001⟩`

In decimal form for the first register, this is:
`|ψ₁⟩ = (1/√8) Σ_{x=0 to 7} |x⟩ ⊗ |1⟩`

**3. Controlled Modular Exponentiation (`|ψ₂⟩`)**

This is the "magic" step. The `C-U` gate entangles the two registers. For each state `|x⟩` in the counting register, the working register is transformed to `|a^x mod N⟩`. We are using `a=7` and `N=15`.

`|ψ₂⟩ = (1/√8) Σ_{x=0 to 7} |x⟩ ⊗ |7^x mod 15⟩`

Let's expand this sum term by term:
*   `x=0`: `|000⟩ ⊗ |7⁰ mod 15⟩ = |000⟩ ⊗ |1⟩`
*   `x=1`: `|001⟩ ⊗ |7¹ mod 15⟩ = |001⟩ ⊗ |7⟩`
*   `x=2`: `|010⟩ ⊗ |7² mod 15⟩ = |010⟩ ⊗ |4⟩`
*   `x=3`: `|011⟩ ⊗ |7³ mod 15⟩ = |011⟩ ⊗ |13⟩`
*   `x=4`: `|100⟩ ⊗ |7⁴ mod 15⟩ = |100⟩ ⊗ |1⟩`
*   `x=5`: `|101⟩ ⊗ |7⁵ mod 15⟩ = |101⟩ ⊗ |7⟩`
*   `x=6`: `|110⟩ ⊗ |7⁶ mod 15⟩ = |110⟩ ⊗ |4⟩`
*   `x=7`: `|111⟩ ⊗ |7⁷ mod 15⟩ = |111⟩ ⊗ |13⟩`

So the full entangled state is:
`|ψ₂⟩ = (1/√8)[ |000⟩|1⟩ + |001⟩|7⟩ + |010⟩|4⟩ + |011⟩|13⟩ + |100⟩|1⟩ + |101⟩|7⟩ + |110⟩|4⟩ + |111⟩|13⟩ ]`

Notice the periodicity! The working register states `|1⟩, |7⟩, |4⟩, |13⟩` repeat. The period is `r=4`.

**4. Inverse Quantum Fourier Transform (`|ψ₃⟩`)**

We now apply the `QFT⁻¹` to the **counting register only**. Its purpose is to take the periodicity (`r=4`) from the entangled state and convert it into high probabilities for specific measurement outcomes. The states that will be amplified are those whose value `c` (from 0 to 7) is close to an integer multiple of `2³/r = 8/4 = 2`.

Therefore, we expect to measure values of `c` that are multiples of 2: **0, 2, 4, or 6**. The `QFT⁻¹` transforms the state such that:

`|ψ₃⟩ ≈ (1/2)[ |000⟩ + |010⟩ + |100⟩ + |110⟩ ] ⊗ |"garbage state"⟩`

(The math is complex, but the result is that the quantum state collapses into a superposition of only the desired outcomes for the counting register.)

**5. Measurement (`c`)**

We measure the counting register. Based on the state `|ψ₃⟩`, we have an equal probability (1/4) of measuring one of the following binary strings:
*   `000` (decimal 0)
*   `010` (decimal 2)
*   `100` (decimal 4)
*   `110` (decimal 6)

Let's say we measure **`c = 6`**.

**6. Final Classical Step**

We now have `N=15`, `a=7`, and a measurement `c=6`. We use the continued fractions algorithm to find `s/r` from the approximation `c / 2³ ≈ s/r`.
*   `6 / 8 = 3 / 4`
*   This gives us a candidate for the period: **`r = 4`**.

We check if `r` is even (it is) and if `a^(r/2) ± 1` is a factor.
*   `a^(r/2) - 1 = 7^(4/2) - 1 = 7² - 1 = 48`
*   `a^(r/2) + 1 = 7^(4/2) + 1 = 7² + 1 = 50`

Now find the factors using the greatest common divisor (GCD):
*   `gcd(48, 15) = 3`
*   `gcd(50, 15) = 5`

**The factors of 15 are 3 and 5.** The algorithm was successful.

Drag to resize

OpenAI

GPT-4.1

Certainly! Let’s visualize the quantum circuit for Shor’s algorithm using **5 qubits** and ket notation.

### Brief Explanation

Shor’s algorithm factors a number \( N \) by reducing the problem to order-finding. The core quantum circuit involves:

1. **Initialization:** Two quantum registers.
   - **First register (for superposition input):** Enough qubits to represent numbers up to \( N^2 \). For our simplified version, **3 qubits**.
   - **Second register (for modular exponentiation value):** Needs enough qubits to store values mod \( N \). For our simplified version, **2 qubits**.

2. **Hadamard gates:** Applied to the first register to create a superposition.

3. **Modular exponentiation:** Controlled application using the first register as controls onto the second register.

4. **Inverse Quantum Fourier Transform (QFT†):** Applied to the first register.

5. **Measurement:** Both registers.

---

### Shor's Circuit with 5 Qubits (in ket notation)

Let’s lay out the 5-qubit circuit:

```
Qubit Index    | Operation Flow

  q[0]         --H--●--------------------QFT†-- M ----->  x₀  [First reg]
                    | 
  q[1]         --H--●--------------------QFT†-- M ----->  x₁  [First reg]
                    |
  q[2]         --H--●--------------------QFT†-- M ----->  x₂  [First reg]
                    |
  q[3]         -----⊕(MOD EXP)--------------- M ----->  y₀  [Second reg]
                    
  q[4]         -----⊕(MOD EXP)--------------- M ----->  y₁  [Second reg]
```

Where:

- `H` is the **Hadamard gate** (creates superposition).
- `●` Connected lines indicate **controlled modular exponentiation** (for simplicity, indicated as a “box” that acts on the second register, controlled by the state of the first).
- `⊕(MOD EXP)` is a placeholder for **modular exponentiation** operation.
- `QFT†` is the **Inverse Quantum Fourier Transform** (on the first three qubits).
- `M` indicates **measurement**.
- `x₀ x₁ x₂` are the classical results from the first register (superposition input).
- `y₀ y₁` are the classical results from the second register (output of modular exponentiation).

---

### Circuit in ASCII/Ket Notation

Using ket notation for initial state:

\[
|q_0\rangle = |0\rangle \\
|q_1\rangle = |0\rangle \\
|q_2\rangle = |0\rangle \\
|q_3\rangle = |1\rangle \\
|q_4\rangle = |0\rangle \\
\]

**Step-by-step circuit:**

```
|0⟩ ---H---●------------------- QFT† --- M ---> x₀
           |                           
|0⟩ ---H---●------------------- QFT† --- M ---> x₁
           |                           
|0⟩ ---H---●------------------- QFT† --- M ---> x₂
           |                     
|1⟩ -----(MODULAR EXP)-------------- M ---> y₀
           
|0⟩ -----(MODULAR EXP)-------------- M ---> y₁
```

- At the start, the register is in \( |00010\rangle \) (for instance).
- Hadamards create a superposition \( \sum_x |x\rangle \).
- Modular exponentiation computes \( |x\rangle|y\rangle \to |x\rangle|a^x \bmod N\rangle \).
- Inverse QFT decodes the periodicity.
- Finally, all qubits are measured.

---

### (Optional) How It Would Look in a Quantum Circuit Drawing

```plaintext
|0⟩ ---H---■------------------------[QFT†]--- M
|0⟩ ---H---■------------------------[QFT†]--- M
|0⟩ ---H---■------------------------[QFT†]--- M
|1⟩ -------┼--[Mod Exp (a^x mod N)]-------- M
|0⟩ -------┼--[Mod Exp (a^x mod N)]-------- M
```

---

### Summary Table

| Qubit | Init. State   | Gates Applied                      | Purpose                  |
|-------|---------------|------------------------------------|--------------------------|
| q[0]  | \(|0\rangle\) | Hadamard, MOD EXP, QFT†, Measure   | 1st reg, superposition   |
| q[1]  | \(|0\rangle\) | Hadamard, MOD EXP, QFT†, Measure   | 1st reg, superposition   |
| q[2]  | \(|0\rangle\) | Hadamard, MOD EXP, QFT†, Measure   | 1st reg, superposition   |
| q[3]  | \(|1\rangle\) | MOD EXP, Measure                   | 2nd reg, function value  |
| q[4]  | \(|0\rangle\) | MOD EXP, Measure                   | 2nd reg, function value  |


---

**In summary:**  
Shor’s algorithm for factoring with 5 qubits (minimal demonstration) uses three qubits for the “input” register and two for the “output.” The circuit is Hadamard gates, modular exponentiation, inverse QFT on the first three, then measurement. If you need an image or LaTeX circuit diagram, let me know!

Drag to resize

Alibaba

Qwen3 235B A22B (Non-reasoning)

Here's a textual visualization of the quantum circuit for **Shor's algorithm** using **5 qubits** (3 in the first register, 2 in the second) and **ket notation**:

---

### **Circuit Structure**
```
q0: |0> --H--•------------------QFT†--M
              |                 
q1: |0> --H--•--•-------------QFT†--M
                 |            
q2: |0> --H--•--•--•----------QFT†--M
              |  |  |         
q3: |0> -------U--U^-controlled-|a^x mod N
q4: |0> ------------------------|a^x mod N
```

---

### **Step-by-Step Ket Notation**

1. **Initial State**  
   All qubits initialized to $ |0\rangle $:  
   $$
   |\psi_0\rangle = |00000\rangle
   $$

2. **Apply Hadamard Gates to First Register (q0–q2)**  
   Creates superposition of all $ 2^3 = 8 $ states:  
   $$
   |\psi_1\rangle = \frac{1}{\sqrt{8}} \left( |000\rangle + |001\rangle + |010\rangle + |011\rangle + |100\rangle + |101\rangle + |110\rangle + |111\rangle \right) \otimes |00\rangle
   $$

3. **Apply Controlled-Modular Exponentiation (Controlled-$ U $)**  
   Entangles the first register with $ |a^x \mod N\rangle $ in the second register:  
   $$
   |\psi_2\rangle = \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle \otimes |a^x \mod N\rangle
   $$
   (Here, $ N $ is the number to factor, and $ a $ is a randomly chosen integer coprime to $ N $.)

4. **Apply Inverse Quantum Fourier Transform (QFT†) to First Register**  
   Converts the superposition into a periodic state:  
   $$
   |\psi_3\rangle = \text{QFT}^\dagger \left( \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle \right) \otimes |a^x \mod N\rangle
   $$
   (The QFT† amplifies the probabilities of measuring the period $ r $ of $ a^x \mod N $.)

5. **Measure First Register (q0–q2)**  
   Collapses to a classical state $ |y\rangle $, which encodes the period $ r $ via continued fractions.

---

### **Key Notes**
- **Registers**:  
  - **First Register (q0–q2)**: 3 qubits for superposition and period estimation.  
  - **Second Register (q3–q4)**: 2 qubits to store $ |a^x \mod N\rangle $.  
- **Modular Exponentiation**: Represented as a black-box controlled-$ U $ operation.  
- **QFT†**: Critical for extracting the period $ r $, which is used classically to factor $ N $.

This structure assumes a simplified example (e.g., $ N = 5 $ or $ N = 6 $) where 2 qubits suffice for the second register. For larger $ N $, more qubits are required.

Drag to resize

DeepSeek

DeepSeek V3 0324

Here's a visualization of a simplified 5-qubit quantum circuit for Shor's algorithm, using ket notation for the qubit states:

```
Qubit Labels: |q₀⟩ (control) |q₁⟩|q₂⟩|q₃⟩|q₄⟩ (work)

Circuit Diagram:

|q₀⟩ ───H─────●──────────────●─────────────── ... ────
              │              │
|q₁⟩ ─────────┼───H───●──────┼─────●─────── ... ────
              │       │      │     │
|q₂⟩ ─────────┼───────┼──H───┼─────┼───●─── ... ────
              │       │      │     │   │
|q₃⟩ ─────────┼───────┼──────┼──H──┼───┼─── ... ────
              │       │      │     │   │
|q₄⟩ ─────────U^(2^0)─U^(2^1)─U^(2^2)─U^(2^3) ... ────
```

Ket Notation Representation:

1. Initialization:
   |ψ₀⟩ = |0⟩⊗|0⟩⊗|0⟩⊗|0⟩⊗|0⟩ = |00000⟩

2. After Hadamard on control qubit:
   |ψ₁⟩ = (|0⟩+|1⟩)/√2 ⊗ |0000⟩ = (|00000⟩ + |10000⟩)/√2

3. After first controlled-U (2⁰):
   |ψ₂⟩ = (|0⟩|0000⟩ + |1⟩U|0000⟩)/√2

4. After Hadamard on |q₁⟩ and controlled-U (2¹):
   |ψ₃⟩ = (|0⟩|0000⟩ + |1⟩U|0000⟩)/√2 ⊗ (|0⟩+|1⟩)/√2
   Then apply controlled-U²...

5. Continue this pattern for modular exponentiation

6. Final state before QFT:
   |ψ⟩ = Σₓ e^(2πiφx)|x⟩|f(x)⟩

Key Components Shown:
- Control qubit |q₀⟩ initialized in superposition
- Work qubits |q₁⟩-|q₄⟩ used for modular exponentiation
- Controlled-U operations where U is the modular multiplication gate
- (Implied) Quantum Fourier Transform at the end (not shown due to space)

Note: A full Shor's implementation would require more qubits for meaningful factorization, but this shows the core pattern scaled to 5 qubits. The actual U gates depend on the specific number N being factored.

Drag to resize

OpenAI

o4-mini (high)

Here is an ASCII sketch of the 5-qubit circuit for the core quantum part of Shor’s algorithm (factoring 15, with base a=7).  We use 3 qubits for the “exponent” register (q₂,q₁,q₀) and 2 qubits for the “auxiliary” register (q₃,q₄).  All kets are written ⎪…⟩.  

Initial state:  
 ⎪000⟩₍₂₁₀₎ ⊗ ⎪01⟩₍₃₄₎  

 q₂ ──⎪0⟩───[H]─────────●────────────────────────[QFT⁻¹]───M──  
                          │  
 q₁ ──⎪0⟩───[H]─────●─────●────────────────────────[QFT⁻¹]───M──  
                     │     │  
 q₀ ──⎪0⟩───[H]───●──●─────●────────────────────────[QFT⁻¹]───M──  
                 │   │     │  
 q₃ ──⎪0⟩────────■───■─────■───────────  
                 │   │     │  
 q₄ ──⎪1⟩────────■───■─────■───────────  

Legend:  
- The first three qubits (q₂,q₁,q₀) start in ⎪000⟩ and each receives a Hadamard [H].  
- The bottom two qubits (q₃,q₄) start in ⎪01⟩ (encoding a¹ mod 15 = 7).  
- The three filled‐circle gates are controls from q₀,q₁,q₂ onto a joint two-qubit box acting on (q₃,q₄) implementing modular multiplication U^{2ʲ} mod 15:  
 • control q₀ → U^{2⁰ mod 15} = U¹  
 • control q₁ → U^{2¹ mod 15} = U²  
 • control q₂ → U^{2² mod 15} = U⁴  
- After these controlled‐U’s, we perform the inverse quantum Fourier transform (QFT⁻¹) on q₂,q₁,q₀ and then measure them (M), yielding an estimate of the period.  

Notes:  
- Boxes [H] and [QFT⁻¹] act only on the single wires they sit on.  
- The three‐wire cluster of ■──■──■ represents the two-qubit modular multiplication gates (one box per control).  
- Classical post-processing on the measured outcome finds the period r and hence the factors of 15.

Drag to resize

Meta

Llama 4 Maverick

## Step 1: Understand Shor's Algorithm and its Quantum Circuit
Shor's algorithm is a quantum algorithm for factorizing a given integer N. It uses a quantum circuit that involves several qubits. For a 5-qubit system, we will have to adjust the algorithm to fit the available qubits. Typically, Shor's algorithm requires more qubits for the period-finding subroutine and additional qubits for the input and output.

## Step 2: Break Down Shor's Algorithm into Components
Shor's algorithm consists of two main parts: a quantum period-finding subroutine and a classical post-processing step. The quantum part involves applying a Hadamard gate to the first register (control qubits), applying a controlled unitary operation (U) that corresponds to the modular exponentiation, and then applying a Quantum Fourier Transform (QFT) to the first register.

## Step 3: Determine the Qubits' Roles
For a simplified 5-qubit system, let's assume the first 3 qubits are used for the control register (for period finding) and the last 2 qubits are used for the work register (to store the result of modular exponentiation). However, for simplicity and due to the constraints of the problem, we'll directly visualize a simplified version.

## Step 4: Visualize the Quantum Circuit
Let's represent the qubits as $|q_1, q_2, q_3, q_4, q_5\rangle$. The first three qubits ($q_1, q_2, q_3$) will be used for the control register, and the last two ($q_4, q_5$) for the work register.

1. **Initial State**: $|0, 0, 0, 0, 0\rangle$
2. **Apply Hadamard Gate to Control Qubits**: $H^{\otimes 3} \otimes I^{\otimes 2} |0, 0, 0, 0, 0\rangle = \frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x, 0, 0\rangle$
3. **Modular Exponentiation (Simplified)**: Apply $U^{x}$ on $|0, 0\rangle$ controlled by $|x\rangle$. For simplicity, let's assume $U$ is a unitary operation representing modular exponentiation.
4. **Quantum Fourier Transform (QFT) on Control Qubits**: Apply $QFT_3$ on $|q_1, q_2, q_3\rangle$.

## Step 5: Representing the Circuit Mathematically
The circuit can be represented as:
1. $|0, 0, 0, 0, 0\rangle$
2. $\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes |0, 0\rangle$ after Hadamard gates.
3. $\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes U^x |0, 0\rangle$ after modular exponentiation.
4. $QFT_3 \otimes I^{\otimes 2} \left(\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes U^x |0, 0\rangle\right)$ after QFT.

## Step 6: Simplify the Visualization
Given the complexity of directly drawing a quantum circuit, we simplify by understanding that the circuit involves:
- Hadamard gates on $q_1, q_2, q_3$.
- Controlled-$U$ operations between $q_1, q_2, q_3$ and $q_4, q_5$, representing modular exponentiation.
- QFT on $q_1, q_2, q_3$.

The final answer is: $\boxed{|q_1, q_2, q_3, q_4, q_5\rangle = \frac{1}{2\sqrt{2}} \sum_{x=0}^{7} QFT_3|x\rangle \otimes U^x |0, 0\rangle}$

Drag to resize

DeepSeek

DeepSeek R1 0528 (May '25)

Response not available

Drag to resize

Anthropic

Claude 4 Sonnet (Non-reasoning)

I'll create a visualization of Shor's algorithm quantum circuit using 5 qubits. For this example, I'll show the circuit for factoring N=15 (which requires 4 qubits for the number and 1 auxiliary qubit for demonstration).

```
Shor's Algorithm Quantum Circuit (N=15, a=2)
===========================================

Initial State: |00000⟩

Qubit 0: |0⟩ ──[H]──●────●────●────●────[QFT†]──[M]
                   │    │    │    │
Qubit 1: |0⟩ ──[H]──┼────●────●────●────[QFT†]──[M]  
                   │    │    │    │
Qubit 2: |0⟩ ──[H]──┼────┼────●────●────[QFT†]──[M]
                   │    │    │    │
Qubit 3: |0⟩ ──[H]──┼────┼────┼────●────[QFT†]──[M]
                   │    │    │    │
Qubit 4: |0⟩ ───────U¹───U²───U⁴───U⁸──────────────[M]

Legend:
[H]     = Hadamard gate
●       = Control qubit
U^k     = Modular exponentiation: |x⟩ → |a^k·x mod N⟩
[QFT†]  = Inverse Quantum Fourier Transform
[M]     = Measurement
```

## State Evolution:

**Step 1 - Initialization:**
```
|ψ₀⟩ = |0000⟩ ⊗ |0001⟩
```

**Step 2 - After Hadamard gates:**
```
|ψ₁⟩ = (1/4)∑(x=0 to 15) |x⟩ ⊗ |0001⟩
    = (1/4)(|0000⟩ + |0001⟩ + |0010⟩ + ... + |1111⟩) ⊗ |0001⟩
```

**Step 3 - After controlled modular exponentiation:**
For a=2, N=15, the function f(x) = 2^x mod 15 has period r=4:
- f(0) = 1, f(1) = 2, f(2) = 4, f(3) = 8
- f(4) = 1, f(5) = 2, f(6) = 4, f(7) = 8, etc.

```
|ψ₂⟩ = (1/4)∑(x=0 to 15) |x⟩ ⊗ |2^x mod 15⟩
```

**Step 4 - After QFT† (before measurement):**
The QFT† creates interference patterns that reveal the period r=4:
```
|ψ₃⟩ = (1/2)(|0000⟩ + |0100⟩ + |1000⟩ + |1100⟩) ⊗ |result⟩
```

## Detailed Circuit Components:

### Controlled Modular Exponentiation Gates:
```
U¹: |x⟩|y⟩ → |x⟩|2¹·y mod 15⟩
U²: |x⟩|y⟩ → |x⟩|2²·y mod 15⟩  
U⁴: |x⟩|y⟩ → |x⟩|2⁴·y mod 15⟩
U⁸: |x⟩|y⟩ → |x⟩|2⁸·y mod 15⟩
```

### Quantum Fourier Transform (QFT†):
```
QFT†|j⟩ = (1/√N)∑(k=0 to N-1) e^(-2πijk/N)|k⟩
```

## Expected Measurement Results:
With high probability, measuring the first 4 qubits yields:
- |0000⟩ (decimal 0)
- |0100⟩ (decimal 4)  
- |1000⟩ (decimal 8)
- |1100⟩ (decimal 12)

These correspond to multiples of N/r = 16/4 = 4, revealing the period r=4.

## Classical Post-Processing:
From period r=4, calculate:
- gcd(2^(4/2) - 1, 15) = gcd(3, 15) = 3
- gcd(2^(4/2) + 1, 15) = gcd(5, 15) = 5

Therefore: **15 = 3 × 5** ✓

This circuit demonstrates the key quantum advantage: the superposition of all computational paths and quantum interference in the QFT† that efficiently reveals the period structure.

Drag to resize

Of course! Visualizing Shor's algorithm is a great way to understand its structure. Let's break it down. Shor's algorithm is used to find the prime factors of a large number, `N`. The quantum part of the algorithm is a "period-finding machine." We will create a circuit to factor the canonical example: **N = 15**. ### A Note on the 5-Qubit Constraint You asked for 5 qubits. A *minimal, functional* circuit to factor N=15 actually requires **7 qubits**: * **Working Register:** To store numbers up to N-1 (i.e., 14), we need 4 qubits ($2^4 = 16$). Let's call this `n = 4`. * **Counting Register:** For a high probability of success, this register should have `2n = 8` qubits. However, we can construct a minimal example with just **3 qubits** ($2^3=8$). Using only 5 qubits is insufficient for a real demonstration of factoring N=15. However, we can create a **conceptual visualization using 5 qubits (2 for counting, 3 for working)** to show the *structure* of the algorithm, and then explain the full 7-qubit process with ket notation. Let's proceed with the **correct 7-qubit version** for clarity, as it allows us to follow the real computational steps. --- ### The Goal: Factoring N=15 1. **Classical Part:** * Pick a random number `a` that is coprime to N. Let's pick **`a = 7`**. * (Check: `gcd(7, 15) = 1`. We're good.) 2. **Quantum Part (The Circuit):** * Find the period `r` of the function `f(x) = a^x mod N`. * This means finding the smallest `r > 0` such that `7^r ≡ 1 (mod 15)`. * The period is `r=4` because: * $7^1 \mod 15 = 7$ * $7^2 \mod 15 = 49 \mod 15 = 4$ * $7^3 \mod 15 = 343 \mod 15 = 13$ * $7^4 \mod 15 = 2401 \mod 15 = 1$ 3. **Classical Part (Post-Processing):** * Use `r` to find the factors of N. --- ### Visualization of the Quantum Circuit (for N=15, a=7) Here is the circuit structure. We will use 3 qubits for the counting register and 4 for the working register. **Register Setup:** * **Counting Register (q₀, q₁, q₂):** Starts as `|000⟩`. Will be used to find the period. * **Working Register (q₃, q₄, q₅, q₆):** Starts as `|0001⟩` (representing the number 1). This is where the `mod 15` calculation happens. ``` ┌───┐ ┌───────┐┌─┐ q₀:|0⟩────┤ H ├───────■─────────────────────────────┤ ├┤M├ ├───┤ │ │ │└╥┘ q₁:|0⟩────┤ H ├───────■─────────────────────────────┤ QFT⁻¹ ├─╫─ ├───┤ │ │ │ ║ q₂:|0⟩────┤ H ├───────■─────────────────────────────┤ ├─╫─ └───┘ ┌─┴─┐ ┌───┐ ┌───┐ ┌───┐ └───────┘ ║ q₃:|0⟩──────────────┤ ├───┤ ├───┤ ├───┤ ├──────────────╫─ q₄:|0⟩──────────────┤ ├───┤ ├───┤ ├───┤ ├──────────────╫─ q₅:|0⟩──────────────┤ U ├───┤ U ├───┤ U ├───┤ U ├──────────────╫─ q₆:|1⟩──────────────┤ ├───┤ ├───┤ ├───┤ ├──────────────╫─ └─┬─┘ └───┘ └───┘ └───┘ ║ │ ║ Control: (q₀) (q₁) (q₂) ║ ║ Output: Classical Bits (c₁, c₂, c₃) ``` **What the gates mean:** * `H`: Hadamard gate. * `QFT⁻¹`: Inverse Quantum Fourier Transform. * `M`: Measurement. * **`C-U` (the big controlled gate):** This is the heart of the algorithm. It's the **Controlled-U** gate for modular exponentiation. * It performs the operation: `|x⟩|y⟩ → |x⟩|a^x * y mod N⟩`. * In our circuit, it's decomposed into controlled operations based on the qubits in the counting register. The first `C-U` is controlled by `q₂`, so it calculates `a^(2^0) = a^1`. The second is controlled by `q₁`, calculating `a^(2^1) = a^2`, and so on. --- ### Step-by-Step Evolution of the Quantum State (using Ket Notation) Let's trace the state of our 7 qubits, `|ψ⟩`, through the circuit. **1. Initialization (`|ψ₀⟩`)** The system starts with the counting register in the state `|000⟩` and the working register in `|0001⟩` (which represents the integer 1). `|ψ₀⟩ = |000⟩ ⊗ |0001⟩` (This is `|0⟩` in the counting register and `|1⟩` in the working register.) **2. Hadamard Gates (`|ψ₁⟩`)** We apply Hadamard gates to each qubit in the counting register. This creates a uniform superposition of all possible values from 0 to 7. `|ψ₁⟩ = (H⊗H⊗H)|000⟩ ⊗ |0001⟩` `|ψ₁⟩ = (1/√8)(|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩) ⊗ |0001⟩` In decimal form for the first register, this is: `|ψ₁⟩ = (1/√8) Σ_{x=0 to 7} |x⟩ ⊗ |1⟩` **3. Controlled Modular Exponentiation (`|ψ₂⟩`)** This is the "magic" step. The `C-U` gate entangles the two registers. For each state `|x⟩` in the counting register, the working register is transformed to `|a^x mod N⟩`. We are using `a=7` and `N=15`. `|ψ₂⟩ = (1/√8) Σ_{x=0 to 7} |x⟩ ⊗ |7^x mod 15⟩` Let's expand this sum term by term: * `x=0`: `|000⟩ ⊗ |7⁰ mod 15⟩ = |000⟩ ⊗ |1⟩` * `x=1`: `|001⟩ ⊗ |7¹ mod 15⟩ = |001⟩ ⊗ |7⟩` * `x=2`: `|010⟩ ⊗ |7² mod 15⟩ = |010⟩ ⊗ |4⟩` * `x=3`: `|011⟩ ⊗ |7³ mod 15⟩ = |011⟩ ⊗ |13⟩` * `x=4`: `|100⟩ ⊗ |7⁴ mod 15⟩ = |100⟩ ⊗ |1⟩` * `x=5`: `|101⟩ ⊗ |7⁵ mod 15⟩ = |101⟩ ⊗ |7⟩` * `x=6`: `|110⟩ ⊗ |7⁶ mod 15⟩ = |110⟩ ⊗ |4⟩` * `x=7`: `|111⟩ ⊗ |7⁷ mod 15⟩ = |111⟩ ⊗ |13⟩` So the full entangled state is: `|ψ₂⟩ = (1/√8)[ |000⟩|1⟩ + |001⟩|7⟩ + |010⟩|4⟩ + |011⟩|13⟩ + |100⟩|1⟩ + |101⟩|7⟩ + |110⟩|4⟩ + |111⟩|13⟩ ]` Notice the periodicity! The working register states `|1⟩, |7⟩, |4⟩, |13⟩` repeat. The period is `r=4`. **4. Inverse Quantum Fourier Transform (`|ψ₃⟩`)** We now apply the `QFT⁻¹` to the **counting register only**. Its purpose is to take the periodicity (`r=4`) from the entangled state and convert it into high probabilities for specific measurement outcomes. The states that will be amplified are those whose value `c` (from 0 to 7) is close to an integer multiple of `2³/r = 8/4 = 2`. Therefore, we expect to measure values of `c` that are multiples of 2: **0, 2, 4, or 6**. The `QFT⁻¹` transforms the state such that: `|ψ₃⟩ ≈ (1/2)[ |000⟩ + |010⟩ + |100⟩ + |110⟩ ] ⊗ |"garbage state"⟩` (The math is complex, but the result is that the quantum state collapses into a superposition of only the desired outcomes for the counting register.) **5. Measurement (`c`)** We measure the counting register. Based on the state `|ψ₃⟩`, we have an equal probability (1/4) of measuring one of the following binary strings: * `000` (decimal 0) * `010` (decimal 2) * `100` (decimal 4) * `110` (decimal 6) Let's say we measure **`c = 6`**. **6. Final Classical Step** We now have `N=15`, `a=7`, and a measurement `c=6`. We use the continued fractions algorithm to find `s/r` from the approximation `c / 2³ ≈ s/r`. * `6 / 8 = 3 / 4` * This gives us a candidate for the period: **`r = 4`**. We check if `r` is even (it is) and if `a^(r/2) ± 1` is a factor. * `a^(r/2) - 1 = 7^(4/2) - 1 = 7² - 1 = 48` * `a^(r/2) + 1 = 7^(4/2) + 1 = 7² + 1 = 50` Now find the factors using the greatest common divisor (GCD): * `gcd(48, 15) = 3` * `gcd(50, 15) = 5` **The factors of 15 are 3 and 5.** The algorithm was successful.

Certainly! Let’s visualize the quantum circuit for Shor’s algorithm using **5 qubits** and ket notation. ### Brief Explanation Shor’s algorithm factors a number $ N $ by reducing the problem to order-finding. The core quantum circuit involves: 1. **Initialization:** Two quantum registers. - **First register (for superposition input):** Enough qubits to represent numbers up to $ N^2 $. For our simplified version, **3 qubits**. - **Second register (for modular exponentiation value):** Needs enough qubits to store values mod $ N $. For our simplified version, **2 qubits**. 2. **Hadamard gates:** Applied to the first register to create a superposition. 3. **Modular exponentiation:** Controlled application using the first register as controls onto the second register. 4. **Inverse Quantum Fourier Transform (QFT†):** Applied to the first register. 5. **Measurement:** Both registers. --- ### Shor's Circuit with 5 Qubits (in ket notation) Let’s lay out the 5-qubit circuit: ``` Qubit Index | Operation Flow q[0] --H--●--------------------QFT†-- M -----> x₀ [First reg] | q[1] --H--●--------------------QFT†-- M -----> x₁ [First reg] | q[2] --H--●--------------------QFT†-- M -----> x₂ [First reg] | q[3] -----⊕(MOD EXP)--------------- M -----> y₀ [Second reg] q[4] -----⊕(MOD EXP)--------------- M -----> y₁ [Second reg] ``` Where: - `H` is the **Hadamard gate** (creates superposition). - `●` Connected lines indicate **controlled modular exponentiation** (for simplicity, indicated as a “box” that acts on the second register, controlled by the state of the first). - `⊕(MOD EXP)` is a placeholder for **modular exponentiation** operation. - `QFT†` is the **Inverse Quantum Fourier Transform** (on the first three qubits). - `M` indicates **measurement**. - `x₀ x₁ x₂` are the classical results from the first register (superposition input). - `y₀ y₁` are the classical results from the second register (output of modular exponentiation). --- ### Circuit in ASCII/Ket Notation Using ket notation for initial state: \[ |q_0\rangle = |0\rangle \\ |q_1\rangle = |0\rangle \\ |q_2\rangle = |0\rangle \\ |q_3\rangle = |1\rangle \\ |q_4\rangle = |0\rangle \\ \] **Step-by-step circuit:** ``` |0⟩ ---H---●------------------- QFT† --- M ---> x₀ | |0⟩ ---H---●------------------- QFT† --- M ---> x₁ | |0⟩ ---H---●------------------- QFT† --- M ---> x₂ | |1⟩ -----(MODULAR EXP)-------------- M ---> y₀ |0⟩ -----(MODULAR EXP)-------------- M ---> y₁ ``` - At the start, the register is in $ |00010\rangle $ (for instance). - Hadamards create a superposition $ \sum_x |x\rangle $. - Modular exponentiation computes $ |x\rangle|y\rangle \to |x\rangle|a^x \bmod N\rangle $. - Inverse QFT decodes the periodicity. - Finally, all qubits are measured. --- ### (Optional) How It Would Look in a Quantum Circuit Drawing ```plaintext |0⟩ ---H---■------------------------[QFT†]--- M |0⟩ ---H---■------------------------[QFT†]--- M |0⟩ ---H---■------------------------[QFT†]--- M |1⟩ -------┼--[Mod Exp (a^x mod N)]-------- M |0⟩ -------┼--[Mod Exp (a^x mod N)]-------- M ``` --- ### Summary Table | Qubit | Init. State | Gates Applied | Purpose | |-------|---------------|------------------------------------|--------------------------| | q[0] | $|0\rangle$ | Hadamard, MOD EXP, QFT†, Measure | 1st reg, superposition | | q[1] | $|0\rangle$ | Hadamard, MOD EXP, QFT†, Measure | 1st reg, superposition | | q[2] | $|0\rangle$ | Hadamard, MOD EXP, QFT†, Measure | 1st reg, superposition | | q[3] | $|1\rangle$ | MOD EXP, Measure | 2nd reg, function value | | q[4] | $|0\rangle$ | MOD EXP, Measure | 2nd reg, function value | --- **In summary:** Shor’s algorithm for factoring with 5 qubits (minimal demonstration) uses three qubits for the “input” register and two for the “output.” The circuit is Hadamard gates, modular exponentiation, inverse QFT on the first three, then measurement. If you need an image or LaTeX circuit diagram, let me know!

Here's a textual visualization of the quantum circuit for **Shor's algorithm** using **5 qubits** (3 in the first register, 2 in the second) and **ket notation**: --- ### **Circuit Structure** ``` q0: |0> --H--•------------------QFT†--M | q1: |0> --H--•--•-------------QFT†--M | q2: |0> --H--•--•--•----------QFT†--M | | | q3: |0> -------U--U^-controlled-|a^x mod N q4: |0> ------------------------|a^x mod N ``` --- ### **Step-by-Step Ket Notation** 1. **Initial State** All qubits initialized to $ |0\rangle $: $$ |\psi_0\rangle = |00000\rangle $$ 2. **Apply Hadamard Gates to First Register (q0–q2)** Creates superposition of all $ 2^3 = 8 $ states: $$ |\psi_1\rangle = \frac{1}{\sqrt{8}} \left( |000\rangle + |001\rangle + |010\rangle + |011\rangle + |100\rangle + |101\rangle + |110\rangle + |111\rangle \right) \otimes |00\rangle $$ 3. **Apply Controlled-Modular Exponentiation (Controlled-$ U $)** Entangles the first register with $ |a^x \mod N\rangle $ in the second register: $$ |\psi_2\rangle = \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle \otimes |a^x \mod N\rangle $$ (Here, $ N $ is the number to factor, and $ a $ is a randomly chosen integer coprime to $ N $.) 4. **Apply Inverse Quantum Fourier Transform (QFT†) to First Register** Converts the superposition into a periodic state: $$ |\psi_3\rangle = \text{QFT}^\dagger \left( \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle \right) \otimes |a^x \mod N\rangle $$ (The QFT† amplifies the probabilities of measuring the period $ r $ of $ a^x \mod N $.) 5. **Measure First Register (q0–q2)** Collapses to a classical state $ |y\rangle $, which encodes the period $ r $ via continued fractions. --- ### **Key Notes** - **Registers**: - **First Register (q0–q2)**: 3 qubits for superposition and period estimation. - **Second Register (q3–q4)**: 2 qubits to store $ |a^x \mod N\rangle $. - **Modular Exponentiation**: Represented as a black-box controlled-$ U $ operation. - **QFT†**: Critical for extracting the period $ r $, which is used classically to factor $ N $. This structure assumes a simplified example (e.g., $ N = 5 $ or $ N = 6 $) where 2 qubits suffice for the second register. For larger $ N $, more qubits are required.

Here's a visualization of a simplified 5-qubit quantum circuit for Shor's algorithm, using ket notation for the qubit states: ``` Qubit Labels: |q₀⟩ (control) |q₁⟩|q₂⟩|q₃⟩|q₄⟩ (work) Circuit Diagram: |q₀⟩ ───H─────●──────────────●─────────────── ... ──── │ │ |q₁⟩ ─────────┼───H───●──────┼─────●─────── ... ──── │ │ │ │ |q₂⟩ ─────────┼───────┼──H───┼─────┼───●─── ... ──── │ │ │ │ │ |q₃⟩ ─────────┼───────┼──────┼──H──┼───┼─── ... ──── │ │ │ │ │ |q₄⟩ ─────────U^(2^0)─U^(2^1)─U^(2^2)─U^(2^3) ... ──── ``` Ket Notation Representation: 1. Initialization: |ψ₀⟩ = |0⟩⊗|0⟩⊗|0⟩⊗|0⟩⊗|0⟩ = |00000⟩ 2. After Hadamard on control qubit: |ψ₁⟩ = (|0⟩+|1⟩)/√2 ⊗ |0000⟩ = (|00000⟩ + |10000⟩)/√2 3. After first controlled-U (2⁰): |ψ₂⟩ = (|0⟩|0000⟩ + |1⟩U|0000⟩)/√2 4. After Hadamard on |q₁⟩ and controlled-U (2¹): |ψ₃⟩ = (|0⟩|0000⟩ + |1⟩U|0000⟩)/√2 ⊗ (|0⟩+|1⟩)/√2 Then apply controlled-U²... 5. Continue this pattern for modular exponentiation 6. Final state before QFT: |ψ⟩ = Σₓ e^(2πiφx)|x⟩|f(x)⟩ Key Components Shown: - Control qubit |q₀⟩ initialized in superposition - Work qubits |q₁⟩-|q₄⟩ used for modular exponentiation - Controlled-U operations where U is the modular multiplication gate - (Implied) Quantum Fourier Transform at the end (not shown due to space) Note: A full Shor's implementation would require more qubits for meaningful factorization, but this shows the core pattern scaled to 5 qubits. The actual U gates depend on the specific number N being factored.

Here is an ASCII sketch of the 5-qubit circuit for the core quantum part of Shor’s algorithm (factoring 15, with base a=7). We use 3 qubits for the “exponent” register (q₂,q₁,q₀) and 2 qubits for the “auxiliary” register (q₃,q₄). All kets are written ⎪…⟩. Initial state: ⎪000⟩₍₂₁₀₎ ⊗ ⎪01⟩₍₃₄₎ q₂ ──⎪0⟩───[H]─────────●────────────────────────[QFT⁻¹]───M── │ q₁ ──⎪0⟩───[H]─────●─────●────────────────────────[QFT⁻¹]───M── │ │ q₀ ──⎪0⟩───[H]───●──●─────●────────────────────────[QFT⁻¹]───M── │ │ │ q₃ ──⎪0⟩────────■───■─────■─────────── │ │ │ q₄ ──⎪1⟩────────■───■─────■─────────── Legend: - The first three qubits (q₂,q₁,q₀) start in ⎪000⟩ and each receives a Hadamard [H]. - The bottom two qubits (q₃,q₄) start in ⎪01⟩ (encoding a¹ mod 15 = 7). - The three filled‐circle gates are controls from q₀,q₁,q₂ onto a joint two-qubit box acting on (q₃,q₄) implementing modular multiplication U^{2ʲ} mod 15: • control q₀ → U^{2⁰ mod 15} = U¹ • control q₁ → U^{2¹ mod 15} = U² • control q₂ → U^{2² mod 15} = U⁴ - After these controlled‐U’s, we perform the inverse quantum Fourier transform (QFT⁻¹) on q₂,q₁,q₀ and then measure them (M), yielding an estimate of the period. Notes: - Boxes [H] and [QFT⁻¹] act only on the single wires they sit on. - The three‐wire cluster of ■──■──■ represents the two-qubit modular multiplication gates (one box per control). - Classical post-processing on the measured outcome finds the period r and hence the factors of 15.

## Step 1: Understand Shor's Algorithm and its Quantum Circuit Shor's algorithm is a quantum algorithm for factorizing a given integer N. It uses a quantum circuit that involves several qubits. For a 5-qubit system, we will have to adjust the algorithm to fit the available qubits. Typically, Shor's algorithm requires more qubits for the period-finding subroutine and additional qubits for the input and output. ## Step 2: Break Down Shor's Algorithm into Components Shor's algorithm consists of two main parts: a quantum period-finding subroutine and a classical post-processing step. The quantum part involves applying a Hadamard gate to the first register (control qubits), applying a controlled unitary operation (U) that corresponds to the modular exponentiation, and then applying a Quantum Fourier Transform (QFT) to the first register. ## Step 3: Determine the Qubits' Roles For a simplified 5-qubit system, let's assume the first 3 qubits are used for the control register (for period finding) and the last 2 qubits are used for the work register (to store the result of modular exponentiation). However, for simplicity and due to the constraints of the problem, we'll directly visualize a simplified version. ## Step 4: Visualize the Quantum Circuit Let's represent the qubits as $|q_1, q_2, q_3, q_4, q_5\rangle$. The first three qubits ($q_1, q_2, q_3$) will be used for the control register, and the last two ($q_4, q_5$) for the work register. 1. **Initial State**: $|0, 0, 0, 0, 0\rangle$ 2. **Apply Hadamard Gate to Control Qubits**: $H^{\otimes 3} \otimes I^{\otimes 2} |0, 0, 0, 0, 0\rangle = \frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x, 0, 0\rangle$ 3. **Modular Exponentiation (Simplified)**: Apply $U^{x}$ on $|0, 0\rangle$ controlled by $|x\rangle$. For simplicity, let's assume $U$ is a unitary operation representing modular exponentiation. 4. **Quantum Fourier Transform (QFT) on Control Qubits**: Apply $QFT_3$ on $|q_1, q_2, q_3\rangle$. ## Step 5: Representing the Circuit Mathematically The circuit can be represented as: 1. $|0, 0, 0, 0, 0\rangle$ 2. $\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes |0, 0\rangle$ after Hadamard gates. 3. $\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes U^x |0, 0\rangle$ after modular exponentiation. 4. $QFT_3 \otimes I^{\otimes 2} \left(\frac{1}{2\sqrt{2}} \sum_{x=0}^{7} |x\rangle \otimes U^x |0, 0\rangle\right)$ after QFT. ## Step 6: Simplify the Visualization Given the complexity of directly drawing a quantum circuit, we simplify by understanding that the circuit involves: - Hadamard gates on $q_1, q_2, q_3$. - Controlled-$U$ operations between $q_1, q_2, q_3$ and $q_4, q_5$, representing modular exponentiation. - QFT on $q_1, q_2, q_3$. The final answer is: $\boxed{|q_1, q_2, q_3, q_4, q_5\rangle = \frac{1}{2\sqrt{2}} \sum_{x=0}^{7} QFT_3|x\rangle \otimes U^x |0, 0\rangle}$

I'll create a visualization of Shor's algorithm quantum circuit using 5 qubits. For this example, I'll show the circuit for factoring N=15 (which requires 4 qubits for the number and 1 auxiliary qubit for demonstration). ``` Shor's Algorithm Quantum Circuit (N=15, a=2) =========================================== Initial State: |00000⟩ Qubit 0: |0⟩ ──[H]──●────●────●────●────[QFT†]──[M] │ │ │ │ Qubit 1: |0⟩ ──[H]──┼────●────●────●────[QFT†]──[M] │ │ │ │ Qubit 2: |0⟩ ──[H]──┼────┼────●────●────[QFT†]──[M] │ │ │ │ Qubit 3: |0⟩ ──[H]──┼────┼────┼────●────[QFT†]──[M] │ │ │ │ Qubit 4: |0⟩ ───────U¹───U²───U⁴───U⁸──────────────[M] Legend: [H] = Hadamard gate ● = Control qubit U^k = Modular exponentiation: |x⟩ → |a^k·x mod N⟩ [QFT†] = Inverse Quantum Fourier Transform [M] = Measurement ``` ## State Evolution: **Step 1 - Initialization:** ``` |ψ₀⟩ = |0000⟩ ⊗ |0001⟩ ``` **Step 2 - After Hadamard gates:** ``` |ψ₁⟩ = (1/4)∑(x=0 to 15) |x⟩ ⊗ |0001⟩ = (1/4)(|0000⟩ + |0001⟩ + |0010⟩ + ... + |1111⟩) ⊗ |0001⟩ ``` **Step 3 - After controlled modular exponentiation:** For a=2, N=15, the function f(x) = 2^x mod 15 has period r=4: - f(0) = 1, f(1) = 2, f(2) = 4, f(3) = 8 - f(4) = 1, f(5) = 2, f(6) = 4, f(7) = 8, etc. ``` |ψ₂⟩ = (1/4)∑(x=0 to 15) |x⟩ ⊗ |2^x mod 15⟩ ``` **Step 4 - After QFT† (before measurement):** The QFT† creates interference patterns that reveal the period r=4: ``` |ψ₃⟩ = (1/2)(|0000⟩ + |0100⟩ + |1000⟩ + |1100⟩) ⊗ |result⟩ ``` ## Detailed Circuit Components: ### Controlled Modular Exponentiation Gates: ``` U¹: |x⟩|y⟩ → |x⟩|2¹·y mod 15⟩ U²: |x⟩|y⟩ → |x⟩|2²·y mod 15⟩ U⁴: |x⟩|y⟩ → |x⟩|2⁴·y mod 15⟩ U⁸: |x⟩|y⟩ → |x⟩|2⁸·y mod 15⟩ ``` ### Quantum Fourier Transform (QFT†): ``` QFT†|j⟩ = (1/√N)∑(k=0 to N-1) e^(-2πijk/N)|k⟩ ``` ## Expected Measurement Results: With high probability, measuring the first 4 qubits yields: - |0000⟩ (decimal 0) - |0100⟩ (decimal 4) - |1000⟩ (decimal 8) - |1100⟩ (decimal 12) These correspond to multiples of N/r = 16/4 = 4, revealing the period r=4. ## Classical Post-Processing: From period r=4, calculate: - gcd(2^(4/2) - 1, 15) = gcd(3, 15) = 3 - gcd(2^(4/2) + 1, 15) = gcd(5, 15) = 5 Therefore: **15 = 3 × 5** ✓ This circuit demonstrates the key quantum advantage: the superposition of all computational paths and quantum interference in the QFT† that efficiently reveals the period structure.