Quantum Computing

A qubit is described by a state such as |ψ> = α|0> + β|1>, where α and β are complex amplitudes and |α|² + |β|² = 1. Measurement gives 0 with probability |α|² and 1 with probability |β|². The useful part is not the slogan that the qubit is both values. The useful part is that amplitudes can rotate, combine, and interfere before measurement.[1][2]

A normal bit is like a light switch: by the time you use it, it is either 0 or 1. A qubit is more like a little arrow whose direction controls the odds of seeing 0 or 1 when you finally measure it. Quantum gates rotate that arrow. When you use more qubits, the arrows live in a much larger mathematical space, and their waves can add together or cancel out.

That cancellation is the whole trick. A useful quantum algorithm is not asking the machine to print every possible answer. It is arranging the rotations so bad possibilities interfere destructively and useful structure gets amplified. Measurement then gives you one classical answer, but the circuit before measurement has tilted the odds toward something worth reading.

Quantum gates are operations on these state vectors. A Hadamard gate can put a basis state into an equal superposition. Phase gates change relative phase. Controlled gates entangle systems so the state of one qubit cannot be fully described without the other. A quantum circuit is a carefully arranged sequence of these transformations followed by measurement.

Because measurement collapses information into classical outcomes, a quantum algorithm has to do something subtle before the final readout. It must make the amplitude of good answers larger and the amplitude of bad answers smaller. That is why good quantum algorithms feel less like brute force and more like choreography.

Classical gates are usually thought of as Boolean functions. Quantum gates are unitary transformations: reversible operations that preserve total probability. That alone changes the design language. You cannot casually erase information inside a quantum circuit the way ordinary software throws away temporary variables. You have to manage reversibility, phase, entanglement, measurement, and noise.

This creates an incredible class of new compute problems. Some of the hard work is not running the algorithm. It is framing the problem so the answer is represented in a structure that interference can amplify. In classical programming, a loop can just test candidate answers. In quantum programming, the art is often building an oracle, encoding the state, preserving coherence, then uncomputing garbage so the final amplitudes still mean what you think they mean.

Grant Sanderson's video on quantum computing is valuable because it refuses to hide the geometric nature of the problem. The state is not a little coin spinning in a cartoon. It is a vector in a huge complex space, and gates move that vector.[3]

Quantum computers are promising when a problem has exploitable mathematical structure. They are not promising merely because the input is large. The famous examples are factoring and discrete logarithms through Shor's algorithm, unstructured search through Grover's algorithm, simulation of quantum systems, and certain optimization, sampling, and linear-algebra-adjacent workloads where the right assumptions hold.[4][5]

Quantum simulation is the most philosophically direct case: nature is quantum, so a controllable quantum system may represent certain physical systems more naturally than a classical approximation. Chemistry, materials, condensed matter, and some energy problems are obvious candidates. That does not make every molecule instantly easy. It means the representation mismatch can be less awful.

Quantum computing is not a silver bullet. It does not make NP-complete problems vanish into polite little checkmarks. It does not accelerate every database, every AI workload, or every cryptographic primitive equally. It does not remove the need for classical compute; in practice quantum systems are controlled, corrected, scheduled, and interpreted by classical systems.

The hardware problem is also brutal. Useful fault-tolerant quantum computing requires error correction, many physical qubits per logical qubit, precise control, low noise, and algorithms whose advantage survives the overhead. The difference between a beautiful theoretical circuit and an economically useful machine is not a rounding error. It is most of the mountain.

Grover's algorithm gives a quadratic speedup for unstructured search. If there are N possible items and one marked answer, a classical blind search takes about N/2 guesses on average. Grover can find the marked item in about O(√N) oracle queries.[5]

The mechanism is amplitude amplification. Start in a uniform superposition over candidates. Use an oracle to flip the phase of the marked state. Then apply a diffusion step that reflects amplitudes about their average. Repeating those two operations rotates the state vector toward the marked answer. Do it too many times and you rotate past it, which is a nice reminder that quantum algorithms are not magic, they are geometry with deadlines.

For security, Grover matters most for symmetric cryptography and hashes. It effectively halves the security exponent: a 256-bit hash target starts to look more like 128-bit work against an ideal large quantum attacker. That is serious, but not the same kind of apocalypse as Shor against RSA or elliptic curves.

Shor's algorithm is the reason public-key cryptography has been losing sleep politely for decades. It can factor integers and compute discrete logarithms in polynomial time on a sufficiently large fault-tolerant quantum computer.[4] RSA relies on factoring being hard. Diffie-Hellman and elliptic-curve cryptography rely on discrete logarithms being hard. Shor attacks that foundation.

For factoring, the key reduction is period finding. Pick a number a relatively prime to N, then study the periodic function f(x) = a^x mod N. A quantum circuit prepares a superposition of inputs, evaluates the function, and uses the quantum Fourier transform to reveal the period r. If r behaves nicely, classical post-processing computes gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) to recover factors.

The weird beauty is that the quantum part is not directly "trying factors." It is extracting periodic structure from amplitudes. The classical part then turns that structure into the answer.

Post-quantum security is the migration from public-key systems vulnerable to Shor toward algorithms believed to resist both classical and quantum attacks. NIST's current standards include ML-KEM for key encapsulation, ML-DSA for digital signatures, and SLH-DSA as a stateless hash-based signature option.[6] The transition matters because encrypted data can be harvested now and decrypted later if a future quantum computer can break the public-key exchange used to protect it.

The key point is selective urgency. Symmetric encryption and hashes can often be strengthened by using larger parameters. Public-key systems based on factoring and discrete logs need replacement. That includes RSA, finite-field Diffie-Hellman, and elliptic-curve signatures and key exchange in many deployed systems.[6][7]

For organizations, the practical work is inventory: where are keys used, where is RSA or ECC embedded, what data has long confidentiality life, which protocols can be upgraded, which vendors are on the critical path, and what hybrid migration path avoids breaking the business while trying to save it.

A sufficiently large fault-tolerant quantum computer running Shor's algorithm would threaten the elliptic-curve signatures Bitcoin uses. Bitcoin uses ECDSA over secp256k1 for many signatures. If an attacker has a public key and enough quantum capability, Shor could derive the corresponding private key.[8]

The nuance matters. Many modern Bitcoin addresses are hashes of public keys, so the public key may not be visible until a coin is spent. That provides some practical delay, not a permanent defense. Reused addresses, old pay-to-public-key outputs, exposed public keys, and transactions sitting in the mempool are more concerning. Grover's algorithm is less catastrophic for SHA-256 because the effective security reduction still leaves a large margin, though mining and hash assumptions would deserve careful review in a post-quantum world.

So the answer is: not an immediate panic, not a fake issue. The credible path is protocol migration to post-quantum signatures, likely with tradeoffs around signature size, compatibility, old coins, and social coordination. As usual in crypto, the math problem is only half the problem.