Generating Quantum Algorithms
Today, the quantum community is focusing on generating bigger, fault-tolerant devices. Say that we did achieve it. How are we going to harness them with just a few quantum algorithms up our sleeves? We need to discover new algorithms, this is what this post is about.
Quantum computing is an entirely different domain of computation. It builds upon the strange properties of quantum systems to get a computational speedup in specific problems, beyond what is capable with present-day classical computers. This has been proven in principle but it hasn’t been realized experimentally, as of now. Quantum computers are in their ‘vacuum tube’ era and reaching up to the capabilities of classical systems will take more time.
Today’s NISQ (noisy intermediate-scale quantum) computers face some major issues of scalability, non-availability of algorithms, and error correction. While making robust hardware is what most research is about, this post introduces the Quantum Algorithm Generator, which essentially would change how we convert a classical algorithm into its quantum equivalent.
Let’s get started.
Quantum Circuits
Like any classical circuit, a quantum circuit consists of input data, processing of that data, and output data. This data is encoded into quantum states, the processing is done on those states, and finally, measurement is done to extract the results of the computation.
Since it is a quantum device, the data and the processing should be relevant to the principles on which the device operates i.e. quantum mechanics. Hence, the inputs and outputs from a quantum computer are quantum states and the processing of those states is done by quantum or unitary operators.
An example — Quantum Adder
Quantum addition works in a similar way as classical addition with binary numbers.
The program for a quantum adder looks to add two numbers utilizing the quantum domain. How do we formulate this problem of adding into quantum states? We encode the inputs, send them through the circuit, and decode the final output states to get the final result.
Suppose we have encoded the operands for our required sum in the quantum state|Ψo⟩ and the final output in the quantum state |Ψf⟩. If we say that the final state |Ψf⟩ is U|Ψo⟩, then solving for U gives us our quantum adder. For example, a simple quantum adder is specified by the following circuit.
What you see above is the circuit for a quantum adder and the realization of the operator U (which is the part between the two barriers). We are interested in figuring out the ‘operator’ through which we are led to the resultant state and how we go about doing it.
Realizing quantum algorithms
Quantum computers aim to help classical computers in certain tasks which just can not be solved efficiently using the present classical model of computation. They provide us with a new way to think about computation and thus solve some specific problems like integer factorization or unstructured search faster than their classical counterparts. Although most quantum algorithms do not have classical counterparts, a classical algorithm may be encoded into quantum equivalents. How do you find a quantum equivalent of a classical algorithm?
Inside a quantum computer, computation is done by manipulating the quantum states of qubits. Formally stating, quantum states evolve by the action of Unitary or Reversible operators and any kind of possible operation on a quantum system has to, generally, follow that law. In quantum computing, we look for ways to convert a classical algorithm to its quantum equivalent by finding out the target unitary operator.
Traditional Methods to find Unitaries
Since there is no specified way developed to find the resultant unitary operator, researchers mostly rely on trial and error or take inspiration from pre-established quantum approaches.
The usual methods that people employ are:
- Using mathematics to find the desired circuit. For example, if you know that the state is currently |B⟩ and it has evolved from state |A⟩ by the action of operator U, we need to find U such that U|A⟩ = |B⟩. This matrix equation is not easy to solve for an increasing number of dimensions.
- Transforming traditional methods and using solutions from the already proposed quantum algorithms is another way to go about generating quantum circuits but is constrained to the available methods.
- Variational algorithms, which allow classical computers and quantum computers to work in tandem to find out the best quantum circuits tuned to a particular problem. These algorithms suffer from the problem of scaling as classical computers have a limit to the number of parameters they can handle.
All the above approaches are essentially heuristic approaches and we wish to ask the question — can we find a way to break this process down into systematic steps? The answer is to let the machines do it for us.
How machines figure out solutions
Very probably, everyone reading this article is somewhat familiar with the idea of machine learning. For those of you who aren’t, it is a field of computer science that lets computers find the rules about how to achieve a result for a problem given that we train it with relevant examples. This image would clear out the above text a bit.
Neural networks are a particular tool employed in this domain and they are currently state of the art when it comes to finding arbitrary rules of a given problem. What all these tools do, is generate a general black box, which is trained on the sample inputs and outputs of the problem that you want to solve. After that phase, you may use that ‘trained’ box to produce the correct outputs you require, given valid inputs.
Why we care about it is because this can be utilized to find the unitary that we are looking for our quantum circuits. The black box produced would simulate that unitary for a given set of inputs and outputs pretty accurately. But that’s a way to figure out how to ‘use’ the rules. You may make a black box that runs on them but the limitation of that tool is that you can’t see how the rules combine to form the black box. You can’t see inside it.
Quantastica’s Algorithm Generator
Quantum Algorithm Generator (QAG) by Quantastica is inspired by the same methodology of machine learning. When given an input quantum state and an output quantum state, it produces the quantum circuit which led you to that desired output state.
It builds upon the limitations of the classical machine learning models by giving you an ‘open box’ instead of a black box. While a neural network would be capable of producing correct output states, it is not possible to actually look at what it has discovered. QAG changes that.
The basic principle behind QAG is letting machines handle the work of identifying algorithms. Think of it like this:
You have a quantum state |A⟩ and a desired output state |B⟩. You are looking to find the unitary operator U which transforms |A⟩ to |B⟩. QAG finds that for you. Its inherent algorithm generates a valid quantum circuit U that generates the state |B⟩ when applied on |A⟩.
Now that we know what QAG is about, let us elaborate on how it works by continuing the simple example of a quantum adder.
Working and Features
Since it is a quantum tool, it makes sense that any kinds of inputs and outputs to the generator are valid quantum states. This brings us to the first important caveat about its working.
If you are trying to find a quantum equivalent of a classical algorithm, there has to be a way to correctly encode your inputs into quantum states before passing them to the QAG. The same follows for the output. If you can find a way to do that, QAG would be able to find a valid quantum circuit for the type of inputs you provide it.
In the below image, we are generating a full quantum adder with binary inputs. The wires going from top to bottom represent the least significant bits, going on to the most significant bits in our circuit. Wire q2 represents the final Cout and q3 represents the Sum.
An essential characteristic of any quantum device is the basic instruction set that it is capable of executing. QAG takes that factor into account and gives a feature of providing a target instruction set. What it means is that whatever instruction set you provide to the QAG, the circuit that it returns is composed of instructions from the target instruction set only. People who are a bit familiar with quantum can appreciate this feature more as this saves the ‘transpilation’ time of the circuit.
Another very important part of the QAG is that it provides the tolerance which is allowed while finding out the circuit. It is just a way to define how closely you want the QAG to identify a circuit given the inputs and outputs. How is this closeness defined? For a candidate circuit, the QAG compares the output that it produces and compares it to the correct output we supply to the QAG in the first place. The more similar this state is to the original output, the better is our estimate.
Lastly, the circuit that is returned, can be converted to executable code for major quantum software development kits by selecting from any of the numerous options that QAG provides.
This short 2-minute video would clear out the process further and you can easily verify that the returned circuit indeed implements the quantum full adder.
Current State
Presently, QAG is limited to simulating up to 6 qubits on a single computer and greater than 6 qubits on a High-Performance Computer.
The QAG comes in a simple interface integrated with Quantastica’s Quantum Programming Studio (QPS) where you can provide classical inputs and outputs in form of a truth table, vectors, unitary operators, and more. QAG transforms all the above types of inputs and outputs into valid quantum states before passing them into the generator to find the final circuit.
Quantastica also provides a REST API for python which goes by the name of quantastica-qps-api for the QPS. This API can be installed via pip and allows users to access the tool via a python environment.
Limitations
The main limitations to the QAG lie in the trade-off between the number of qubits it can simulate, the size of its instruction set, and how deep the quantum circuit is allowed to be formed. These features become the three basic elements of defining something called the generator volume and how to increase this generator volume is an avid area of research for the QAG.
Impact of QAG
Why do we care about the reverse engineering of circuits?
The first and foremost reason is to realize quantum equivalents of classical functions where the function is very hard to simulate for large inputs but we know the answers for smaller ones. What we want is to be able to realize those functions in a quantum computer so that the limitations of the classical model of computation are overcome. Take for example the Travelling Salesman Problem, where the problem statement is simple but generalizing is quite hard. We just can’t run the algorithms for such problems classically as we don’t have enough resources to go about simulating them. If quantum algorithms for those problems are found, we may be able to solve many problems that are just ‘too hard’ for classical machines.
The second and a bit far-fetched reason is related to the efficient simulation of physical systems. How have proteins folded to generate the current state? Can we know how a nitrogenous compound evolves to its current molecular structure? All these problems extremely hard to simulate on classical devices and are related to identifying the process. QAG is the first stepping stone towards the path of efficient drug discovery and greener fertilizers.
Actual Results
The QAG is not just a proposed tool but has been recently used by the Oak Ridge National Laboratory in one of their recent papers. They used QAG as a circuit-making tool for theoretically realizing a unitary matrix and comparing the experimental results with it. Another proof of concept is depicted in this video where IBM’s 2020 quantum challenge has been solved optimally by the QAG in under 2 minutes.
The above examples are just a handful of domains and problems where algorithm generation or process finding is essential for better research or more efficient solutions. Given the characteristics and features of the QAG, it surely has the ability to play a key role in further development in every one of them.
To conclude, we highlighted the main problems associated with realizing quantum advantage and introduced the notion of Quantum Algorithm Generation. We looked at how Quantastica’s QAG is the first step towards making that advantage real and established the fact that algorithm generation is an important initial stage to realize much greater goals of efficient simulation. Stay tuned for more exciting posts by Quantum Untangled.
