Glued Trees Algorithm

[adam-godel]

This is my submission of a quantum circuit implementation of the glued trees algorithm using Classiq. I have been working on this project more heavily in this repository, but I have created a condensed version of it that fits nicely in one Jupyter notebook and more thoroughly explains the theory behind the algorithm.

Similar to many of the other algorithms on the Classiq library, I have also included the qmod files for all of my executions in the circuits subdirectory, with the simulator results automatically saved to the results subdirectory upon execution. In addition, the graphs of the results using Matplotlib are saved in the figures subdirectory.

Please let me know if you have any questions and feel free to make any changes you need. I hope to see my algorithm added to the Classiq library soon!

[review-notebook-app[bot]]

Check out this pull request on 

See visual diffs & provide feedback on Jupyter Notebooks.

---

Powered by ReviewNB

[adam-godel]

I have made a new commit addressing all of the comments. Please let me know if there is anything else I need to do. Thank you!

[adam-godel]

I believe you are correct, and I have re-examined the paper carefully and came up with an approach that I believe now works while preserving the oracular setting of the problem.

The $N \times N$ matrix $\mathbf{A}$ is now created directly from a NetworkX graph of the glued trees for a given size, and using Cholesky decomposition, I get a new square matrix. This resulting matrix, however, can't be used to form the block Hamiltonian since the resulting matrix $\mathbf{H}$ wouldn't be a power of two. I resolve this by padding my matrix $\mathbf{B}$ with 4 columns of zeroes, resulting in a matrix of size $N \times (N+4)$. I think this is a valid approach as $\mathbf{B}\mathbf{B}^ ✝ =\mathbf{A}$. Since $N=2^{n+1}-2$, the resulting matrix $\mathbf{H}$ will be a square matrix with side length $2N+4=2^{n+2}$. This means that a glued trees system of size $n$ can be simulated using $n+2$ qubits.

Even though state preparation would be required for a general case of simulating coupled harmonic oscillators, I don't think it's needed for the glued trees algorithm since the quantum state corresponds to the vector $(\dot{\vec{x}}(t), i\mathbf{B}^✝ \vec{x}(t))^T$, which will initially just be $(1,0,\dots,0)^T$. Please let me know if I'm wrong, though. Additionally, I think the highest 4 possible quantum states won't correspond to the state of the oscillators in the system due to the padding I did for the matrix $\mathbf{B}$ to get a Hamiltonian with a proper size. The quantum state we are interested in should now be $|N-1\rangle$, which should correspond to $|\dot{\vec{x}}_N(t)|$.

Please read through my Jupyter notebook and let me know if there are any issues with my new approach. Thank you so much for your help so far, I really appreciate it :)

[orsa-classiq]

Amazing work for the update! Now I think it looks very good and also accurate.

The only thing is that when I try to run run_range(10), the command c = SparsePauliOp.from_operator(H) runs more than 10 minutes without finishing.

Please make sure that there will be a version that will run and work for no more than 5 minutes. The rest can be leaved in a comment.

Maybe if you take care for the sparse nature of the matrix you can do it faster. you can also pre-calculate the strings and save them to a file that will be a commited, with the option to calculate it again in the notebook

[orsa-classiq]

Also - there is a deprecation warning: "The scipy.sparse array containers will be used instead of matrices in Networkx 3.0. Use to_scipy_sparse_array instead."

[adam-godel]

Thank you! I'm glad it works properly now. The problem with running the Qiskit function is very odd, I was able to run it for 10 qubits in only a few seconds. Perhaps it has to do with an installation error for Qiskit? The deprecation error for NetworkX is due to the fact that Classiq requires NetworkX < 3.0, so I made it work for that version as opposed to installing a new version that could clash with Classiq's dependencies.

Regardless, to make things simpler, I have simply created a cache with the Pauli lists for 10 and 20 qubits (the examples used in the notebook) so importing Qiskit and NetworkX is optional. All of the extra libraries imported should be standard for Python now. Please let me know if you encounter any other issues with the imports or anything else in the notebook.

[orsa-classiq]

@adam-godel what version of qiskit did you use? I'm quite surprised that it took so fast for you

[adam-godel]

@orsa-classiq I used the latest version of Qiskit (1.1.0) and was able to run the pauli_str function for both 10 and 11 qubits in a few seconds on my M1 MacBook Pro. 12 and 13 qubits run in a few minutes and higher values take much longer than that.

I noticed that the GitHub actions test is giving a FileNotFound error when trying to open the glued_trees_cache.json file, do you know why this is? If I try to run python -m pytest tests locally, the tests all pass with no errors. If there are no errors or other issues, I think my algorithm should be ready for submission.

[orsa-classiq]

OK, we've done it! Fabulous work, well done on the work @adam-godel

I think the qiskit version indeed explains the time difference, as our testing environment uses older version of it, and they improved this logic not long ago. For now, until we will update the testing environment, we will leave it with the cache workaround.