In short: A quantum computer does not try every answer at once; it evolves a vector of complex amplitudes through reversible unitary gates and uses interference so that wrong answers cancel, which speeds up only specific problem structures.
Two different ways to hold state
A classical machine with n bits is in exactly one of 2n configurations at any instant. Your laptop's 64-bit register holds one definite value, and every flip-flop in a Synopsys Design Compiler netlist is a 0 or a 1 on each clock edge. You can copy it, read it a million times, and it never changes because you looked.
A register of n qubits is described by 2n complex amplitudes, one per basis string, whose squared magnitudes sum to 1. Three qubits need 8 amplitudes; 50 qubits need about 1015. That exponential description is real, but it is a description of the state, not a stock of usable answers. The distinction between a single bit and a single qubit is covered in qubit vs bit; here we focus on what changes when you compute with many of them.
Key fact: Simulating n qubits classically takes memory proportional to 2n. At 16 bytes per amplitude, 30 qubits need 16 GiB, and 50 qubits need roughly 16 petabytes. This is why classical simulation hits a wall near 45 to 50 qubits.
Reversibility: gates that cannot throw information away
A classical AND gate maps two inputs to one output, so from a 0 output you cannot recover which of three input pairs occurred. Information is erased, and Landauer's principle says erasing a bit costs at least kT ln 2 of heat, about 3 zeptojoules at room temperature. Real CMOS dissipates many orders of magnitude more, so this is a theoretical floor rather than a design constraint in Cadence or Siemens flows.
Quantum gates are unitary: the matrix U satisfies U†U = I, so every gate is invertible and total probability is preserved. A Hadamard followed by another Hadamard returns the original state exactly. To compute irreversible functions, you embed them reversibly using ancilla qubits, as in the Toffoli gate (a controlled-controlled-NOT) which is universal for reversible classical logic. The only irreversible step is measurement, which collapses the state.
- Classical: AND, OR, NAND lose information; NOT and CNOT do not.
- Quantum: all gates reversible; measurement is the irreversible step.
- Consequence: you cannot clone an unknown quantum state (the no-cloning theorem), so there is no fan-out wire like in digital logic.
Where the "tries all answers" myth comes from
Apply a Hadamard to each of n qubits starting from all zeros and you get an equal-weight superposition over all 2n strings. Feed that to a function oracle and the output state contains f(x) for every x entangled with x. That is the phrase "quantum parallelism," and it is technically accurate and widely misleading.
The catch is readout. Measuring returns one random x with its f(x), no better than running the function once on a random input. The skill of a quantum algorithm lies in arranging phases so that amplitudes of wrong answers cancel (destructive interference) while the right one grows (constructive interference) before you measure.
Key fact: Grover's search over N items needs about (π/4)√N oracle calls. For N = 1012 that is roughly 785,000 queries versus about 1012 classically on average 5 x 1011. A square-root gain, not "all at once".
Watching amplitude rotate
Geometrically, Grover's iteration is a rotation in a two-dimensional plane spanned by "marked" and "unmarked" states. Each step rotates the state vector by a fixed angle toward the marked axis; overshoot and the probability falls again. The animation below shows one qubit's state vector being rotated, which is the same unitary mechanics in miniature.
Complexity classes: what is actually claimed
Classical efficient computation is P (deterministic) and BPP (randomised, bounded error). Its quantum counterpart is BQP: problems solvable in polynomial time by a quantum circuit with error at most 1/3. We know P ⊆ BPP ⊆ BQP ⊆ PSPACE. Whether BQP contains NP-complete problems is not known, and most researchers believe it does not.
| Problem | Best classical | Quantum | Gain |
|---|---|---|---|
| Unstructured search | O(N) | O(√N), Grover | Quadratic |
| Factoring an n-bit integer | Sub-exponential (number field sieve) | Polynomial, Shor | Super-polynomial, unproven for classical lower bound |
| Simulating quantum chemistry | Exponential in size | Polynomial | Exponential (expected) |
| NP-complete (SAT, routing) | Exponential (believed) | No known poly-time | At most quadratic generic |
This is why EDA problems like placement, routing or SAT-based equivalence checking in Synopsys Formality or Cadence Conformal are not about to be "solved at once". At best a generic speedup is quadratic, and error correction overhead (thousands of physical qubits per logical qubit) can erase it for years.
What you should say in an interview
- State space is exponential to describe, but readout gives n classical bits per run.
- Speedup needs structure: periodicity (Shor), amplitude amplification (Grover), or simulating quantum systems.
- Reversibility is a feature of the model; irreversibility enters only via measurement.
- Quantum computers are not faster general-purpose machines. They are accelerators for narrow problems, much as a GPU is for matrix work.
If you design chips, the closest parallel is that cryo-CMOS control logic and FPGA-based pulse sequencers for qubits are classical hardware problems, and teams such as Avecas VLSI design services work on exactly that mixed-signal side. For the hardware side, see our primer on quantum gates explained, and for structured training in digital and VLSI fundamentals, browse the CourseTron courses.
Ready to go deeper? Join the CourseTron quantum computing course for guided circuits, worked algorithms and interview practice. See the courses.
Frequently asked questions
Does a quantum computer test all possible answers at once?
No. It prepares a superposition and evolves amplitudes, but a measurement returns only one outcome. Useful algorithms use interference so the correct outcome has high probability.
Why must quantum gates be reversible?
Quantum evolution is unitary, which preserves total probability and is invertible. Irreversible logic is emulated by adding ancilla qubits, as with the Toffoli gate.
Can quantum computers solve NP-complete problems quickly?
Not as far as anyone knows. Generic search gains only a quadratic speedup, and BQP is not known to contain NP-complete problems.
Is BQP bigger than P?
Probably, because factoring is in BQP but not known to be in P. This is not formally proven, since a classical lower bound for factoring is unknown.