7.5 Superposition Encoding
As developed in [312, 319], it is possible to build such a superposition of data in time that is linear in the number of points and features. We consider again a dataset D := (x1,…,xM), with xk := (x1k,…,xnk) ∈{0,1}n for each k = 1,…,M. We use a quantum system of the form
where the left-most part with n qubits is called the loading register while the right-most one (also with n qubits) is the storage register. The middle one is an ancilla register that will be used to control manipulations between the loading and storage registers. The encoding algorithm works recursively. We first apply an Hadamard gate to the second ancilla qubit and store the first data point x1 into the storage register. Since
this can be achieved (after the Hadamard operation) by applying the unitary operator
controlled with the second ancilla qubit, and the resulting quantum state reads
This can easily be turned (see the proof...
