Quantum Amplitude Amplification

Section IV: DQAA

Back to Survey

Distributed Quantum AA

Shatter the hardware limits of the NISQ era. Redistribute the computational workload of standard amplitude amplification across multiple smaller quantum processors without losing the optimal quadratic speedup.

Architectural Distribution

Standard amplitude amplification for a search space of size N=2nN=2^n requires an nn-qubit register. On NISQ (Noisy Intermediate-Scale Quantum)The current era of quantum computers. They have a decent number of qubits, but they are 'noisy'—meaning they easily lose their quantum state (decoherence) and make errors because they lack perfect error correction. hardware, this is difficult to maintain coherently. DQAA solves this by Partitioning the Search Space. The global nn-qubit problem is divided into 2j2^j sub-functions using a jj-bit prefix, and distributed across multiple quantum computers operating on only njn-j suffix qubits each.
Real Life: Instead of forcing one giant supercomputer to search a database of size N, we split the database into multiple smaller shards and assign each shard to a smaller, cheaper computer to search simultaneously.
Subspace Size=2njNodes=2j\text{Subspace Size} = 2^{n-j} \quad \text{Nodes} = 2^j
Step 1 of 4
Result
Global monolithic problem (N=2ⁿ). High qubit overhead.