So, recently I started working with the Qiskit, a python library for quantum computing. Thankfully, it allows to simulate a few qubits on local devices, so I didn't go broke after a few sessions.
Anyways, there is a model, called NAND trees. A NAND tree is basically a binary tree where every branch combines the two values below it using a NAND gate. The input bits sit at the leaves, and for the script to work upward until it gets a single value at the root. For a small tree this is easy, but for bigger trees, as more and more values need to be checked, it can get quite computationally expensive.
So, this is where the quantum computers can help. Instead of calculating from bottom to the top, the tree is turned into a graph and the different routes through it become paths that a quantum state can evolve across. A line, or "runway", is attached to the root of the tree, and the input bits change the connections near the leaves. The output after this operation is different depending on NAND tree, which allows to calculate them.
I build the tree and runway as one graph, encode the input at the leaves, and send a quantum wave packet toward the tree. The wave spreads across the available paths, interferes, and the amount transmitted or reflected is used to predict the NAND-tree result.
So, that's what i tried to reproduce in my project.
Although it is still experimental, but prototype works like a pleasure. Although technically unlimited, the algorithm is not implemented perfectly, so there are issues with scalability, but experimental trees for up-to 8 leaves work perfectly! But, the more leaves are added, the more time and resources are required, so sadly it's just an experiment as of now.
But any feedback will be helpful, as this may allow us to fully reproduce the algorithm!
here's the project, with the deeper explanation of algorithm too: https://github.com/mncrftfrcnm/qiskit-nand-tree-implementation
Thank you for reading!
