Fitting the algorithm to the quantum computer, and vice versa

When Cinderella lost her shoe, the solutions did not have any degree of freedom. There was only one woman - so the legend goes - that could comfortably wear the magical shoe.

Fortunately, when trying to create a fit between an algorithm and a quantum computer, there are many more degrees of freedom.

The need to make sure there is 'enough computer' to run the algorithm is symptomatic to the current limited state of quantum computers. When there are fewer than 100 qubits and when the qubits are noisy, not every algorithm can successfully run.

There are two motivations for finding a fit: The first is to run a given algorithm on an existing quantum computer. The second is to understand how large a quantum computer needs to be to run a particular version of the algorithm.

What can be done to find the fit? Quite a few things, even if staying purely in the realm of quantum computing:

• Simplify the algorithm.
• Use a computer with more qubits.
• Trade off qubits for circuit depth: sometimes, if additional qubits are available, allowing for more ancilla qubits, the circuit can become shallower and thus less susceptible to noise.
• Reduce the desired accuracy. For instance, state preparation (the process of loading probability mass functions into qubits) is an important steps in many algorithms, but perhaps the values don't need to be 99.9% accurate and 97% accuracy can suffice as well.
• Change the order of operations. For instance (see this previous post) when calculating a*a-b*b one could first calculate a*a, then calculate and b*b from it, but one could also rewrite this as (a+b)*(a-b) and perhaps that yields a more efficient implementation.
• Identify qubits that are no longer required at some point in the algorithm and reuse them.

This fitting process is not just academic. Even if you are sure that the desired algorithm does not fit in today's quantum computers, you might want to know how large the computer needs to be to run it, and thus be able to extrapolate how far in the future might this solution be feasible.

The point is that fitting is important, but might require a lot of experimentation. However, such experimentation is very difficult to do using gate-level software design tools. This is one reason that we are so excited about the Classiq quantum algorithm design platform, because it lets the designer change the constraints at will and then automatically labors to find a solution that meets these constraints.

For instance, see the video below on finding the sweet spot for state preparation

‍