Information Encoding: Basis Encoding

This is the first proper episode of the series. If you're starting here, there's a short intro a step before it.

A couple of assumptions: you've seen some machine learning and a little introductory quantum computing. As in the intro, everything here lives in the CQ box — classical data, quantum learning device.

Before the topic itself, here's the shape of a supervised quantum learning algorithm. A (binary) quantum classifier is three well-defined pieces:

• Encoding function — maps a classical data point x to a quantum representation ρx.
• State-evolving function — a unitary U that evolves one quantum state into another.
• Decision rule — reads the evolved state and returns a label.

Why encoding even matters

You can't just take a CSV of classical data and pour it into a quantum model. Your world and the world the model runs in are different; something has to happen at the meeting point, and that something is data encoding. How classical information is represented inside a quantum computer sets the stage for which algorithms — and which speed-ups — are even possible. So it's worth getting right.

The commonly used methods are:

Basis encoding

The computational basis state of an n-qubit system stands in for a classical n-bit string. Each classical bit is literally replaced by a qubit, and the computation can then act on many bit-strings at once, in superposition.

Amplitude encoding

As the name suggests, a normalised real vector is written into the amplitudes of the quantum state. It's elegant but uncommon in practice now, with two real limits: you can't perform non-linear (non-unitary) operations, and normalising the amplitudes costs you a degree of freedom relative to the original data. (Hint to see the lost freedom: a normalised 2-D vector is just (cosθ, sinθ).)

Qsample encoding

Given a discrete distribution p[1], …, p[2n] over bit-strings, you prepare an n-qubit state whose amplitudes are the square-roots of those probabilities. The resulting state is sometimes called a qsample.

Dynamic encoding

Because unitary operators only represent a restricted class of matrices, it's handy to associate a Hamiltonian H with a matrix A. If A isn't Hermitian, you encode it inside a larger Hermitian object and only read off the part you need.

Angle encoding

The classical vector is written into the phase angles of an N-qubit state, one angle per qubit. For a feature vector x = [x1, …, xN] the mapping sends each component to a rotation angle. It's simple and has picked up a lot of attention in recent work.

Which of these works best depends heavily on the learning algorithm downstream — some encodings pair beautifully with some algorithms and badly with others. From here on, the focus is basis encoding.

Building basis encoding

A strategy for this was introduced by Ventura, Martinez, and others (in "Quantum associative memory" and "Probabilistic quantum memories"). To keep things simple, take binary features — one bit per feature.

We work with a register of the form: a loading register of N qubits, an ancilla register (a helper whose contents we treat as scratch at the end), and an N-qubit storage register. The patterns get written into the storage register one at a time, each step extending a growing superposition of stored patterns.

The loop, in outline:

• Op 1 — Hadamard on the second qubit of the ancilla, splitting the state into two "branches" (a memory branch and a processing branch).
• Op 2 — Write the next pattern into the loading register (both branches), using X gates where the input bits are 1.
• Op 3 — Copy the pattern into the processing branch's storage register with CNOTs, controlled on the second ancilla bit so only the processing branch is touched.
• Op 4 — Flip the first ancilla bit of the processing branch (CNOT controlled by the second ancilla bit).
• Op 5 — A special unitary on the second ancilla bit, controlled by the first, that splits the processing branch into two sub-branches — one destined to join the memory, one carried forward to the next iteration. The unitary's angle depends on μ = M + 1 − (m + 1).
• Op 6 — Merge the right sub-branch into the memory branch, then uncompute the loading and processing scratch back to the ground state, ready for the next pattern.

The whole procedure runs in O(MN) steps to succeed with certainty, for M patterns of N bits.

There have been several nice architectural proposals for quantum random-access memory (qRAM) — for instance the 2008 paper "Quantum Random Access Memory" — though a practical hardware implementation is still an open problem.

That's it for this one. I'll close with a line Feynman liked: the same key that opens the gates of heaven opens the gates of hell — and so it is with science.