umma.dev

Before Grover's patent, the best known classical algorithm for searching an unsorted database of N items required O(N) steps in the worst case. Lov Grover, working at Bell Labs, showed that a quantum computer could find the item in O(√N) steps. Search a billion-item database classically and you could check five hundred million entries. Grover's algorithm does it in roughly thirty-two thousand quantum steps. This quadratic speedup is provably optimal - no quantum algorithm can do better for unstructured search.

The mechanism is a process called amplitude amplification. A quantum system can exist in a superposition of all N possible states simultaneously. Grover's algorithm initialises this superposition and then applies two operations repeatedly:

• An oracle that flips the sign of the amplitude for the target item, and a diffusion operator that inverts all amplitudes around their average. Each repetition constructively interferes to increase the probability of the target state and destructively interferes to suppress everything else. After O(√N) applications, measuring the quantum system yields the correct answer with high probability.

The patent's figures describe the circuit structure of both the oracle and the diffusion operator. The oracle is problem-specific. It encodes whatever condition "this is the item I'm looking for" - while the diffusion operator is fixed. This separation is what makes the algorithm general. Any search problem expressible as a yes/no oracle can plug into the Grover framework and get the quadratic speedup for free.

Grover filed in 1996, the year after publishing the algorithm at a conference. Lucent held the patent as part of its Bell Labs portfolio. The practical applications extend well beyond database search. Any problem reducible to finding a satisfying assignment (cryptographic key search, constraint satisfaction, optimisation) can in principle benefit from Grover's approach.

RSA encryption, which secures most internet traffic, relies on the computational hardness of factoring large numbers. Multiplying two large primes together is fast; working backwards from the product to recover the primes is believed to be infeasible for classical computers as the numbers grow. The best classical algorithms take roughly exponential time in the number of digits. Peter Shor's 1994 result, patented in 1995, is the reason the words "quantum computer" and "encryption" appear in the same sentence so frequently. He proved that a quantum computer could factor integers in polynomial time.

The algorithm works by converting the factoring problem into a period-finding problem. For a chosen number a and the integer to be factored N, the function f(x) = a^x mod N is periodic - it repeats with some period r. Find r, and you can recover the prime factors of N with high probability using classical arithmetic. The quantum step is finding r efficiently. Shor's circuit applies the quantum Fourier transform, the quantum analogue of the discrete Fourier transform, to extract the period from a superposition of function values. The quantum Fourier transform runs in O((log N)²) steps where the classical equivalent scales exponentially, and this is where the advantage comes from.

The patent's central figure shows the modular exponentiation circuit that constructs the superposition of function values and the quantum Fourier transform stage that extracts the period. The circuit requires a number of qubits proportional to the number of bits in N, and requires those qubits to maintain coherence throughout the entire computation - a hardware demand that still exceeds what any current quantum processor can deliver at cryptographically relevant key sizes.

AT&T held the patent through its Bell Labs research operation. The filing predates the term "cryptographically relevant quantum computer" but the implication was immediately understood by the cryptography community. NIST began its post-quantum cryptography standardisation project in 2016, explicitly motivated by Shor's result, and finalised the first post-quantum standards in 2024.

Shor and Grover worked on paper. D-Wave's patent is a blueprint for physical hardware. Founded in British Columbia in 1999, D-Wave took a different approach to building a quantum computer than the gate-model architecture implied by Shor's and Grover's circuits. Rather than implementing arbitrary quantum circuits with precise gate operations, D-Wave built a quantum annealer; a processor designed specifically to solve optimisation problems by exploiting quantum tunnelling.

The patent describes a processor built from superconducting qubits arranged in a specific topology, with programmable couplers between them. Each qubit is a superconducting loop that can carry current clockwise or anticlockwise, the two states representing 0 and 1. The couplers between qubits can be set to either encourage or discourage neighbouring qubits from aligning. Setting the couplings encodes an optimisation problem and the physics of the system then does the work. Quantum tunnelling allows the processor to escape local minima in the energy landscape in a way that classical simulated annealing cannot, in principle reaching the global minimum faster.

D-Wave sold its first system to Lockheed Martin in 2011 for approximately ten million dollars. Google and NASA purchased a D-Wave 2 in 2013 for use at the Quantum Artificial Intelligence Lab. The processor was the first commercially sold quantum computing system, which made D-Wave both famous and controversial. Physicists debated for years whether the device was exploiting genuine quantum effects or whether a classical optimiser could match its performance. Studies published between 2013 and 2016 found mixed results; the consensus settled around the device being quantum in its physical mechanism while offering limited advantage over classical heuristics on the problems tested.

What the patent represents is the first time anyone sold a quantum processor as a commercial product. The hardware architecture it describes (superconducting flux qubits, programmable couplers, a dedicated chip topology for quadratic unconstrained binary optimisation) established the vocabulary for a generation of quantum annealing research and influenced the designs that followed from companies including Fujitsu, Hitachi and Toshiba.