Algorithm

Q-Alchemy Algorithm

Q-Alchemy solves the bottleneck of bringing classical data into the quantum processor. In technical terms, this is called Quantum State Preparation.

Usually, this is considered a “hard problem” in the sense that if you have N elements of a vector, you need about N operations to “copy” that data into the quantum computer.

Many quantum algorithms that show speed-ups require data to be present as quantum states. Yes, there are few exceptions, but for many quantum machine learning and stochastic simulation tasks, as well as inversion of matrix, speed-ups depend on the presence of quantum data.

Q-Tucker

Our current algorithm is based on Q-Tucker, an iterative Tucker-decomposition method for quantum state preparation. Instead of recursively splitting the state into only two parts at a time, Q-Tucker looks for a multi-part structure that matches the entanglement pattern of the target state and then builds the circuit layer by layer.

The idea is simple: write the target state as a Tucker decomposition with a smaller core state and a collection of block-local operators. If the core is still too far from the all-zero reference state, repeat the same reasoning on the new core. Each iteration removes another layer of entanglement structure from the problem and turns it into a new set of local factors plus a smaller residual core.

In the figure above, the first decomposition is not yet good enough, so the algorithm continues. After a few iterations, the final core is already close enough to the all-zero reference state with respect to the chosen fidelity target. At that point, the remaining core-preparation block can be dropped, and the extracted factors are composed into the final circuit in reverse order.

This is where Q-Tucker becomes useful in practice: it gives a deterministic way to trade fidelity for circuit cost while exploiting the global entanglement structure of the state. In other words, instead of trying to prepare the whole state at once, the algorithm repeatedly peels off structured layers until the leftover core is simple enough.

This is quite a computationally complex task, so doing so will usually not make for a quantum speed-up in the end. It helps however in two ways:

one can use approximations to encode a state more successfully on a NISQ device, see the figure below for an illustration
one can encode an approximation to repeatedly re-create a quantum state as cheaply as possible.

In particular, the second application is a first glance of a Q-RAM.

The reason for this is simple: you can repeatedly create a state with known fidelity loss and a known complexity.

The next step: create a database with a bunch of quantum states you repeatedly need for your experiments.

Q-Alchemy can be your database