Quantum Algorithm Generator
Quantum Algorithm Generator
We have automated process of quantum algorithm design. See how it works in 5 easy steps:
Similar to classical machine learning, input to our tool is a training set. So we don’t even need to know the classical solution for the problem - all we need is example data. If we know classical function - even better, then we can generate a high quality training set and use it as input.
From each row in a dataset (each example) we need to produce a pair of state vectors:
in first state vector we encode input values (features)
in second state vector we encode output values (labels)
That way, we create as many pairs of state vectors as many rows in the dataset.
At this point we need to choose how we will encode values into state vectors. This is actually the hardest part of the whole process. If you choose the wrong encoding scheme, generator will not be able to find a solution.
At this point, we are searching for a answer to one of two questions:
1.) Which single unitary matrix multiplied with prepared state Ψ will result in final state Ψ′ for each pair?
OR
2.) Which single circuit when executed on prepared state Ψ will produce final state Ψ′ for each pair?
That is two strategies and which one we will choose depends on what we will do with the resulting circuit. If we wish to scale-up to many qubits, then we need to produce as efficient circuits as possible, so we choose strategy 2.
For each strategy, we have developed multiple solvers using different techniques:
1.) For finding unitary matrices we made an efficient algorithm, but this way we don’t directly produce a circuit: we need to decompose the resulting matrix first. Decomposition techniques usually return a sub-optimal circuit with many gates. This is not necessarily bad, but for automatic scaling in later steps, it is essential to start with optimal circuits.
2.) Instead matrix, we prefer to directly find optimal (or as efficient as possible) circuits, so we made following solvers:
Brute force: returns optimal circuit but is limited due to the number of variations. Perfect if the problem can be solved with a small and shallow circuit.
Heuristics: in some cases returns sub-optimal circuits, but still better than output from matrix decomposition.
Heuristics + ML: can reach bigger circuits, but sub-optimal.
If we are happy with the resulting circuit then this is the end. But if we want to scale-up to many qubits, then we need to repeat steps 1–3 at least twice, each time with one qubit more. For example: if we encoded data into 4-qubit vectors then we have 4-qubit circuit(s). Now, we need to repeat the same with 5-qubits and 6-qubits.
Finally, when we have 3 sets of circuits (with n, n+1 and n+2 qubits), we are ready for the next step: a post processing tool which we call “Autoscaler”.
Autoscaler is exploiting two facts:
1.) If we observe unitary matrices of the same algorithm with different numbers of qubits, we can see that values are following a pattern. From the pattern it is impossible to predict exactly the next bigger matrix, but we have a good hint about it. This is useful input to our heuristics algorithm.
2.) If we observe circuits with different numbers of qubits, we can spot the pattern on how gates are arranged, and thus we can predict how the next bigger circuit could be assembled. This is true only when we have optimal circuits at input (returned by brute force or heuristic solver).
If an autoscaler can find the pattern, then it can produce a circuit with many qubits (100’s of qubits on a laptop).
In the following 5-minute video you can see the entire process: Quantum Fourier Transform (QFT) algorithm is reverse-engineered from classical Fast Fourier Transform (FFT) function. Generated dataset is encoded into 2, 3, and 4-Qubit vectors and resulting circuits are automatically scaled-up to 50 Qubits:
