Exponential Quantum Speedup on Even Today’s Quantum Computers: Glued Trees Algorithm

An implementation of the glued trees algorithm can be found in the Classiq library and documentation. To learn more about the glued trees problem, you can also visit the Glued Trees website.

One of the biggest challenges in the field of quantum computing today is how relatively rudimentary the available hardware is. While quantum hardware has greatly improved over the past few years, it remains difficult to run most quantum algorithms at a scale where the quantum advantage is evident.

Even so, there are some algorithms that can run effectively, even on today’s quantum computers. One of these algorithms, offering an exponential quantum speedup, asks us to consider two binary trees “glued” together, where each node at the end of one tree is connected to two random nodes on the other tree.

Suppose each node has a secret key, and there is a machine (known as an oracle) that takes in a node’s secret key and returns the keys of its neighbors. The central question of the glued trees problem is this: given the entrance node’s key, how can you find the exit node’s key as efficiently as possible?

The key issue with this setup, and the reason it cannot be efficiently solved on a classical computer, is that you don’t actually know what nodes the keys belong to. Once you reach the web of random connections, you can’t tell whether you’re going towards the exit node or away from it until you actually reach it. On a classical computer, in the worst case, you will have to check every node in the glued trees structure.

In this article, I will outline the quantum approach for solving the glued trees problem, discuss how to implement it using Classiq, highlight how it can be solved on even today’s quantum computers, and consider what the future holds for the glued trees algorithm and other algorithms like it.

It should be noted that the glued trees problem was first posed in the October 2002 paper titled “Exponential algorithmic speedup by a quantum walk” by Childs, et al., but this article will discuss the algorithm for solving the problem outlined by the December 2023 paper titled “Exponential Quantum Speedup in Simulating Coupled Classical Oscillators” by Babbush, et al.

How does the glued trees algorithm work?

While at first glance the glued trees problem seems reminiscent of graph problems from computer science and mathematics, it is actually Newtonian mechanics that will help us implement an efficient algorithm. Let’s imagine the glued trees structure as a system of balls and springs, where the nodes are the balls and the edges are the springs. If we push the ball representing the entrance node, that motion will propagate and eventually affect the exit node.

We can represent this system of balls and springs as an adjacency matrix of our graph with a random ordering of nodes. We can then create a block Hamiltonian from this matrix and use Hamiltonian simulation to generate a quantum state modeling the displacement and speed of each oscillator.

We can then set up our quantum state to begin with a push to the oscillator representing the entrance node. This push will propagate column by column through the glued trees system, such that if the number of columns in a single tree is N, a spike in the speed of the exit node will be observed at time 2N. We can leverage this principle using a quantum computer to speed up the time complexity of our algorithm from exponential to linear time! Assuming the secret keys are bitstring values, we simply observe which bitstring has a spike at time 2N, and we will have found the secret key of the exit node efficiently.

How is the glued trees algorithm implemented?

The glued trees algorithm can be implemented very effectively using Classiq. Given a block Hamiltonian representing our glued trees structure (generated using an external library such as NumPy), we can perform Pauli decomposition using one of Classiq’s built-in functions to get a Pauli list. We need to perform this step since a Pauli list is the Hamiltonian format Classiq’s Hamiltonian simulation function takes in. We can then use Classiq’s Hamiltonian simulation function to get a measurement of the quantum state at a given time.

In my implementation, I assemble several different quantum circuits representing different times around 2N so the spike in the quantum state representing the exit node can be clearly observed. While my implementation uses a linear ordering of nodes for demonstration, so we know clearly where the exit node is and can observe the spike for that specific state, the algorithm can be implemented with any ordering of nodes using Classiq’s built-in SDK or IDE functions.

How can it be solved on today’s quantum hardware?

The major problem with this approach is that the Pauli lists can grow very large for high qubit sizes, representing large glued trees structures. My solution for this was to create ad hoc Pauli list cropping and approximation algorithms, trimming down the potentially very large Pauli lists to a manageable size while keeping the important information contained by the data and avoiding generating Pauli lists for high qubit sizes at all by using approximations based on the Pauli lists for smaller qubit sizes.

As better quantum hardware is developed, quantum computers are able to tolerate a higher circuit depth, meaning that they can handle larger Pauli list inputs. This means that while we need to use heavily trimmed down Pauli lists to run the glued trees algorithm on today’s quantum hardware, future quantum computers will be able to run the algorithm more accurately since less data will have to be removed.

What can the glued trees algorithm be used for?

Currently, there are no known applications of the glued trees algorithm. It is used as a toy problem to demonstrate an exponential quantum speedup using the approach of simulating coupled harmonic oscillators, as it is relatively easy to set up. 

However, the glued trees problem is just one example of a graph problem that can be translated into a system of coupled harmonic oscillators and simulated efficiently on a quantum computer. Perhaps, in the future, more interesting examples will be discovered with strong real-world applications. Regardless, the glued trees algorithm remains a unique and interesting case of a graph problem, Newtonian mechanics, and quantum computing coming together to produce an exponential quantum speedup on even today’s quantum computers.

An implementation of the glued trees algorithm can be found in the Classiq library and documentation. To learn more about the glued trees problem, you can also visit the Glued Trees website.