preview_publication_notebook.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Quantum Machine learning in NISQ era](https://my.rolos.com/public/project/qml_algs_review)\n",
    "<img src=\"https://www.microsoft.com/en-us/research/uploads/prod/2022/03/Quantum-blog_ChetanNayak_03-2022_1400x788.jpg\" height=250>\n",
    "<img src=\"https://pennylane.ai/images/qml/whatisqml/QML_optimization.svg\" height=250>\n",
    "*\n",
    "\n",
    "In this repo presented several algorithms for quantum computers that have a hope for achieving advantage over classical models at least in some tasks in Noisy Intermediate Scale Quantum (NISQ) era or in nearest future.\n",
    "\n",
    "**Abstract:**\\\n",
    "Quantum machine learning. Quantum systems are fundamentally difficult to simulate using classical approaches. The dimension of the state of a quantum system grows exponentially with the number of computational units. The use of quantum systems as a computing platform opens up access to a whole class of algorithms. So, very effective machine learning algorithms may be found that were considered impossible without a quantum computer, as, for example, happened with the problem of factoring numbers from cryptography. The development and search for such algorithms is the subject of the field of quantum machine learning and this review.\n",
    "\n",
    "Review is devided into these main parts:\n",
    "\n",
    "1. **QML frameworks**  \n",
    "  Firstly tools for running quantum algorithms by simulation or by real quantum computers. Frameworks' abilities and limitations are presented.\n",
    "1. **Continuous Variable Quantum Computing**  \n",
    "  Foundations of photonic approach to quantum computing with infinite dimensional qumodes instead of 2-dim qubits. \n",
    "2. **Generative models**\n",
    "   - **Quantum Recurrent Unit on Gaussian platform**  \n",
    "   Continuous variable based algorithm used for text translation.\n",
    "   - **Quantum GAN-s**  \n",
    "   Algorithms with widely believed exponential advantage over classical counterparts.   \n",
    "3. **Category theory and ZX-calculus**     \n",
    "    Mathematically justified diagrammatic language for writing quantum circuits\n",
    "4. **Quantum Graph classification models**  \n",
    "Exponential advantage due to parallel processing of subgraphs. And natural quantum graph embedding based on number of perfect matchings in subgraphs. \n",
    "\n",
    "\\* images from [1](https://www.microsoft.com/en-us/research/uploads/prod/2022/03/Quantum-blog_ChetanNayak_03-2022_1400x788.jpg) and [2](https://pennylane.ai/images/qml/whatisqml/QML_optimization.svg)\n",
    "\n",
    "All these topics discussions with our code, where needed, are located in the corresponding folders inside rolos project **https://my.rolos.com/public/project/qml_algs_review** . Follow the link to copy project.\n",
    "\n",
    "Below you can see only `Generative models` part as a preview."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generative models"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Recurrent Unit on Gaussian platform\n",
    "\n",
    "Contextual Recurrent Network was proposed in (Anschuetz et al. 2023) as an evolution and development of ideas from (Arute et al. 2019). Arute and others considered k-gram quantum models. They showed, that quantum based modification of Bayesian network performs better, than it's classical counterpart.\n",
    "\n",
    "<!-- ![Performance plots](https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/QBayCorrResults.png)\\ -->\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/QBayCorrResults.png width=500>\\\n",
    "Comparison between classical and quantum model from (Arute et al. 2019).\n",
    "\n",
    "This improvement was explained with quantum correlation, which are hard to capture using classical models.\n",
    "Authors also provide a proof of expressive power separation in absolute perfect case. They demonstrate, that classical model with the same parameters won't be able to achieve finite KL divergence, while quantum, due to quantum nonlocality and contextuality, at least in theory is able.\n",
    "\n",
    "Anschuetz et al generalized this proof for neural networks. Quantum model, that they proposed is continuous variable(CV) based. So it is designed to use photonic quantum computer, there instead of every qubit one quantum harmonic oscillator is used.\n",
    "### QRNN architecture\n",
    "For simulation and general simplicity author limit model to only gaussian states. State of CV device can be represented by very difficult nongaussian Wigner quasiprobability function. But initial vacuum state is just a gaussian with zero mean and unit dispersion. So if only gaussian operations are used (operations that transform gaussian to gaussian. e.g. shifting or squeezing), state will keep being gaussian. \n",
    "\n",
    "So if device has $n$ qumods, it's state is fully characterized by vector of means of length $n$ and $n\\times n$ symmetric matrix of covariances. In experiments simulation, that stores these numbers is used.\n",
    "Then evolution of system is described not by specific set of quantum operators (gates), but by general gaussian unitary operation. In fact just square matrix $W$ with size $n+m$ (where n -- hidden state size, and m -- output size). It is the most general gaussian operation, that can be applied to such system. And this matrix is learned with gradient based technic.\n",
    "\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/qrnn_visual.png width=500>\\\n",
    "Authors visualization of model (Anschuetz et al. 2023)\n",
    "\n",
    "\n",
    "To feed the input data to the model, additional $m$ qumods are allocate in quantum device. Input is translated into covariance matrix and means of $m$ qumods via classical fully connected layers. $n$ memory qumod states are also additionally shifted with result of applying another fully connected layer to the input.\n",
    "Finally the hole $n+m$ size system is transformed with $(n+m) \\times (n+m)$ matrix $W$. This mixed memorized information with information obtained on current step.\n",
    "\n",
    "To get output from this model, expectation values on temporal $m$ qumods are measured.\n",
    "\n",
    "\n",
    "As a result QRNN performs in natural language translation task slightly better, than classical models in terms of final KL divergence.\\\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/qrnn_res.png?0 width=500> <img src=\"img/CRNN_plot.png\" height=285>\\\n",
    "Author's(left) and our(right) results of models comparison. \n",
    "\n",
    "Independent implementation of QRNN, is presented in `QRNN` folder. It shows results similar to ones reported by the authors.\n",
    "The exact values are a bit different, which is probably due to implementation details not described in the article. For instance text tokenization and preprocessing, model initialization and  regularization, that turned out to be necessary according to our experiments. But the overall trend and quantum advantage were confirmed.\n",
    "\n",
    "Our results are available in wandb platform https://wandb.ai/amirfvb/CRNN_translate"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum GAN-s\n",
    "\n",
    "The starting point of using quantum models for generative tasks was done by two articles published together (Dallaire-Demers and Killoran 2018) more practical and (Lloyd and Weedbrook 2018) more theoretical one.\n",
    "\n",
    "Authors claimed that quantum models may have an exponential advantage over classical models.\n",
    "\n",
    "This advantage comes from the fact, that measuring quantum system produces a random sample from exponentially big Hilbert Space.\n",
    "\n",
    "These have more theoretical importance than practical, because sampling itself is rarely used in quantum machine learning. Most approaches (see for example [pennylane demos](https://pennylane.ai/qml/demonstrations/quantum-machine-learning) ) utilize expectation values of output over each qubit. On the one hand expectation value approach doesn't fully explore the potential of quantum computer. For example it fully ignores quantum correlations over different qubits. But on the other hand this approach is more practical. \n",
    "\n",
    "To estimate probabilities of each outcome on real quantum computer, you need exponentially many samples (to keep statistical error $1/\\sqrt{n}$ constant with exponentially increasing number of outcomes). At the same time this makes expectation value more noise resistent, which is vital property in NISQ era. Outcomes themselves are only finite set, while in many practical tasks continuous model prediction (like expectation value) is required.\n",
    "And another significant benefit of expectation value is differentiability. There is a parameter shift technic that replaces infinitely small difference in gradient definition with constant difference. So parameter shift technic makes gradient estimation base on medium number of samples averaging possible. \n",
    "\n",
    "Despite these difficulties, there are several attempts to demonstrate any quantum advantage with generative models on practical tasks.\n",
    "\n",
    "### Molecules generation\n",
    "\n",
    "One of the attempts is done in QuMolGAN paper (Li, Topaloglu, and Ghosh 2021). Authors took classical GAN model for generating molecules MolGAN (N. De Cao, De Cao, and Kipf 2018), and inserted small (2-4 qubit) quantum circuit in the beginning of the generator. After the quantum circuit goes normal classical layers. That's why authors call their model Quantum GAN with hybrid generator.\n",
    "\n",
    "Authors conclude, that their quantum model is more efficient, than classical one. And quantum model can be reduced to only 15% of parameters to show performance comparable with results of nonreduced classical model. \n",
    "\n",
    "During training stage Fréchet distance was measured (see figure below)\n",
    "\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/qumolgan_a_plots.png width=500>\\\n",
    "authors plot with learning of quantum and classical GANs.\n",
    "\n",
    "By dint of code, provided by author, we reproduced model learning.\n",
    "\n",
    "Unfortunately, proper results visualization shows, that there is no significant advantage of quantum model over comparable classical counterpart.\n",
    "\n",
    "In terms of Fréchet distance Quantum Mean Reduced (MR) model shows even worse performance, than Classical MR model, which can be seen on smoothed plots below\n",
    "\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/qumolgan_my_plots.png?0 width=500>\n",
    "\n",
    "Moreover, plot of validity score (fraction of valid molecules from generated) shows, that for all models after certain moment there are only vanishingly few number of valid molecules.\n",
    "\n",
    "<img src=https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/qumolgan_my_plots_validity.png width=500>\n",
    "\n",
    "In QuMolGAN quantum part was used as a parameterized quantum circuit (PQC), which means, that expectation values were used as a quantum circuit output. In such configuration output is fully determined by parameters of PQC (angles of qubit rotations). To get any randomness, required for generative model, part of the parameters were replaced with random numbers. In this sense, model work pretty like classical GANs, that just transform input distribution to some distribution similar to target one.\n",
    "\n",
    "Another worth mentioning technic, used in this paper is patching of quantum circuit. \n",
    "\n",
    "To generate random vector of specific size with quantum circuit, this vector is divided into $k$ equal parts. And each part is generated separately with small quantum circuits. This approach gives less expressive, as it is a strong restriction to possible circuits width, and size of used Hilbert space is rather small. But it can be necessary in circumstances of NISQ era with quantum devices strongly limited in number of physical qubits, and with classical simulators limited with number of achievable qubits to simulate. With constant device requirement this technic increases dimensionality of output to values closer to practically applicable. \n",
    "\n",
    "With molecule generation this idea hasn't shown any advantage, but it was successfully applied in earlier work (Huang et al. 2021).\n",
    "\n",
    "### Entire Image Generation\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/patched_gan.png\" width=300>\\\n",
    "authors visualization of their model\n",
    "\n",
    "Patch technic was applied to generate raw images of digits without any classical postprocessing. Even with patch simplification, authors had to downscale images to 8x8 pixels.\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/101.png\" width=900>\\\n",
    "Authors results of generating 0 and 1 digits.\n",
    "\n",
    "Authors use very simple quantum circuit, and they supply classical random noise to get random output. But remarkably they use probabilities of each outcome as an output. Not expectation values, like in many other works. 5 qubits was used, one of which is ancillary, and 4 output qubits. This gives $2^4=16$ output values. Ancillary qubit gives additional nonlinearity for measured output. As mentioned above, this increases required number of measurements (authors used 3000 samples). But it exponentially increases dimensionality of output data and better unleashes potential of quantum computer.\n",
    "\n",
    "### Compressed images generation\n",
    "\n",
    "In QuGAN paper (Stein et al. 2021) authors compressed digits images to low dimensional (2-4 dimensions) space by principal component analysis (PCA). This makes the task extremely simple, but at the same time more controllable and convenient for experiments.\n",
    "\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/real.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/1.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/2.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/3.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/4.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/6.png\" height=80>\\\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/10.png\" height=80>\\\n",
    "Demonstration of PCA compression + decompression with different numbers of dimension.\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/pca_dist.png\" height=300>\\\n",
    "Distribution of PCA compressed data points (first 2 dimensions)\n",
    "\n",
    "On the picture above you can see visualization of all 10 digits, but only three digits (3,6,9) where used in experiments.\n",
    "\n",
    "#### Model architecture\n",
    "In some sense this model is the most quantum among discussed here. It doesn't use classical random noise as an input, but uses quantum random. But they use quantum random in quite specific way.\n",
    "For $n$ dimensional compression $n$ qubit circuit is used. Instead of estimating expectation value over qubits by averaging hight number(~1000) of samples, they average medium (20-30) number of samples. So to certain extend this produces expectation value with significant statistical uncertainty. This results in some distribution. In corner case of 1 sample procedure will result in discrete probability distribution over single measurement outcome ($2^n$ series of \"0\" and \"1\"). Corner case of averaging over $\\inf$ samples results in one real number from [0, 1] over each of $n$ dimensions. \n",
    "Something in between with $m$ samples will result in discrete distribution(binomial distribution) over $m+1$ equally spaced values over each dimension. As it is an averaging of the samples from constant distribution, according to central limit theorem it approaches normal distribution quite fast. \n",
    "This means, that such models won't be able to approximate any complicated distribution far from unimodel \"normal like\" distribution. And furthermore width of distribution (mathematically speaking \"dispersion\") is mostly determined by number of samples. And number as far as it is integer it can't be learned efficiently with gradient decent. \n",
    "\n",
    "Discriminator architecture is also worth mentioning. Discriminator is quantum and represented by another PQC. Discriminator produces $n$ qubits state vector and accesses generator prediction via dot product in Hilbert space. Dot product value is used as a loss function of discriminator and generator. \n",
    "Real data samples are fed to discriminator in the same way after encoding to quantum state. They are encoded by simple single qubit rotations so that expectation values over qubits are equal to true values of data sample.   \n",
    "\n",
    "#### Experiments\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f27334cc67f0675854cfce04df67f6facd5b95de/img/pca_author.png\" height=400>\\\n",
    "author's results visualization\n",
    "\n",
    "Authors report significant advantage of quantum model over classical GAN in terms of both number of parameters and visual correctness (see figure above)\n",
    "Source code for quantum model was provided, but due to it's low quality, some error and controversial choice of quantum framework it was reproduced, fixed and complemented by us. Pennylane framework was used instead of qiskit.\n",
    "\n",
    "Code is available in `QuGAN` folder\n",
    "\n",
    "It shows, that with right hyperparameter adjust 20 parameter classical generator can approximate distribution much better, than authors of the article showed.\n",
    "\n",
    "||Classical|Hybrid (Q-Gen, C-Disc)|\n",
    "|---|---|---|\n",
    "|image|<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/fc391708c2130e3da4f03f06ea14368b2ba989c6/img/dft_contourf_c_20_params_id=73.png\" height=150>|<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f316ee2f2ab15db3c29e327e55b20bde75d3dae0/img/dft_contourf_h_6_params_id=65.png\" height=150>|\n",
    "|hellinger_dist|0.24|0.24|\n",
    "|# Gen. params| 20| 6 |\n",
    "\n",
    "different generative models prediction results\n",
    "\n",
    "Although hybrid model finally has smaller hellinger distance, it can learn only simple distributions similar to normal distribution. And as width of distribution can't be learned by model and is determined by the number of averaged samples, it requires search of this hyperparameter optimal value.\n",
    "\n",
    "Fully quantum model(QuGAN), presented in (Stein et al. 2021) suffers from several problems with discriminator. \n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f316ee2f2ab15db3c29e327e55b20bde75d3dae0/img/QuGAN_discrim.png\" width=500>\\\n",
    "author's visualization of quantum discrimination\n",
    "\n",
    "Firstly, as quantum discriminator accesses directly quantum state, produced by generator, it has no information about sampling, that is used afterwords. In other words discriminator sees only mean value of generated distribution.\n",
    "\n",
    "Secondly, which is partially saves from previous problem, but still not really good, discriminator output in this architecture is just scalar product between generator output and discriminator state. So loss profile can't be difficult or even can't converge to uniform distribution (see figure below).\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/Hacker1337/QML_review/f316ee2f2ab15db3c29e327e55b20bde75d3dae0/img/media_images_disciminator_predictions_500_fd43005df664f4b57759.png\" width=300> <br>\n",
    "discriminator predictions. Lighter == higher probability of being fake\n",
    "\n",
    "\n",
    "All results are available in wandb platform https://wandb.ai/amirfvb/QuGAN-mnist\n",
    "\n",
    "\n",
    "## Conclusion\n",
    "\n",
    "Currently quantum machine learning as well as quantum computers technologies are in their infancy. Classical computers have many decades of development and furthermore quantum platform is fundamentally much more difficult to work with. While pure algorithmic problems like number factoring can be proven to have better asymptotic on quantum computers without having any quantum computer, data driven approaches don't have strong guarantees and only experiments can show their real performance. Therefore it is currently unclear whether quantum machine learning algorithms are scalable enough to overcome classical ones at some point.  \n",
    "\n",
    "Nevertheless the research is actively underway and even with current simulators there are tasks that can be solved.\n",
    "\n",
    "### Reference:\n",
    "\n",
    "Anschuetz, Eric R., Hong-Ye Hu, Jin-Long Huang, and Xun Gao. 2023. “Interpretable Quantum Advantage in Neural Sequence Learning.” PRX Quantum 4 (2): 020338. https://doi.org/10.1103/PRXQuantum.4.020338.\n",
    "\n",
    "Arute, Frank, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, et al. 2019. “Quantum Supremacy Using a Programmable Superconducting Processor.” Nature 574 (7779): 505–10. https://doi.org/10.1038/s41586-019-1666-5.\n",
    "\n",
    "\n",
    "Dallaire-Demers, Pierre-Luc, and Nathan Killoran. 2018. “Quantum Generative Adversarial Networks.” Physical Review A 98 (1): 012324. https://doi.org/10.1103/PhysRevA.98.012324.\n",
    "\n",
    "Lloyd, Seth, and Christian Weedbrook. 2018. “Quantum Generative Adversarial Learning.” Physical Review Letters 121 (4): 040502–040502. https://doi.org/10.1103/physrevlett.121.040502.\n",
    "\n",
    "Li, Junde, Rasit Topaloglu, and Swaroop Ghosh. 2021. “(QuMolGAN) Quantum Generative Models for Small Molecule Drug Discovery.” arXiv. http://arxiv.org/abs/2101.03438.\n",
    "\n",
    "N. De Cao, Nicola De Cao, and Thomas Kipf. 2018. “MolGAN: An Implicit Generative Model for Small Molecular Graphs.” ArXiv: Machine Learning, May. https://arxiv.org/abs/1805.11973.\n",
    "\n",
    "Huang, He-Liang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, et al. 2021. “Experimental Quantum Generative Adversarial Networks for Image Generation.” Physical Review Applied 16 (2): 024051. https://doi.org/10.1103/PhysRevApplied.16.024051.\n",
    "\n",
    "Stein, Samuel A., Betis Baheri, Daniel Chen, Ying Mao, Qiang Guan, Ang Li, Bo Fang, and Shuai Xu. 2021. “QuGAN: A Quantum State Fidelity Based Generative Adversarial Network.” In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 71–81. https://doi.org/10.1109/QCE52317.2021.00023.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For the rest of the material follow the link to rolos project https://my.rolos.com/public/project/qml_algs_review"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}