All-to-All Connectivity Advantage

Compare circuit depth on connected vs. linear qubit topologies.

All-to-All Connectivity Advantage

The Routing Problem

Real quantum hardware has limited qubit connectivity. When an algorithm needs a two-qubit gate between non-adjacent qubits, the compiler must insert SWAP gates to move quantum states to adjacent positions.

Each SWAP decomposes into 3 CNOT gates:

SWAP(a, b) = CX(a,b) CX(b,a) CX(a,b)

So a single SWAP costs: 3 extra gates, 2 extra circuit depth layers, and significant noise (3x the error of one CNOT).

Linear vs. All-to-All Topology

Superconducting (linear chain): Qubits are arranged in a line or 2D grid. Only adjacent qubits can interact. Long-range gates require routing.

Trapped ion (all-to-all): Any two ions can interact directly via the Molmer-Sorensen gate. No routing overhead.

Example: Entangling Non-Adjacent Qubits

Goal: Entangle qubit 0 and qubit 2 on a 3-qubit system.

Linear topology (q0 - q1 - q2):

Total: 1 H + 3 CNOTs + 1 CNOT = 5 gates

1.H(0)
2.SWAP(q1, q2): cx(1,2), cx(2,1), cx(1,2), moves q2's state to position q1
3.CX(0, 1): now q0 is adjacent to old q2's state

All-to-all topology:

Total: 1 H + 1 CNOT = 2 gates

1.H(0)
2.CX(0, 2): direct interaction, no routing

Circuit Depth Comparison

For a quantum algorithm on n qubits requiring k long-range gates, SWAP overhead roughly doubles the circuit depth on linear topology. For complex algorithms:

Algorithm	Linear topology depth	All-to-all depth
GHZ state	n-1 CNOTs	n-1 CNOTs (same, chain is fine)
QAOA on complete graph	$O (n^{2})$ CNOTs	$O (n)$ CNOTs
QFT	$O (n^{2})$ CNOTs with SWAPs	$O (n^{2})$ CNOTs direct
Quantum chemistry	2-5x overhead	No overhead

For NISQ hardware with limited coherence, SWAP overhead is the difference between a circuit that runs and one that is completely dominated by noise.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Hardware & NISQ

Explore the physics of real quantum computers, understand noise, and learn near-term algorithms designed for today's noisy hardware.

Previous lessonCircuit Depth Analysis Next lessonSWAP Networks: Routing on Linear Topology

This lesson is part of Pro

Unlock Quantum Hardware & NISQ and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground