challenge-2024.09-sep/challenge-2024.09-sep.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "71e0f671-360a-4ea6-b108-88a138481789",
   "metadata": {},
   "source": [
    "<svg width=\"225\" height=\"27\" viewBox=\"0 0 225 27\" fill=\"none\" xmlns=\"http://www.w3.org/2000/svg\">\n",
    "  <path\n",
    "    d=\"M52.7346 0.00200942C54.6105 0.00823099 56.4615 0.432011 58.1533 1.2426C59.845 2.05318 61.3351 3.23024 62.5154 4.68834L58.9085 7.90032C58.1538 6.9955 57.2098 6.26723 56.1431 5.76685C55.0764 5.26647 53.9129 5.00616 52.7346 5.00427C51.7011 5.01585 50.6803 5.23431 49.7326 5.64676C48.7849 6.05921 47.9293 6.6573 47.2165 7.40574C46.5036 8.15417 45.9479 9.0378 45.582 10.0045C45.2162 10.9712 45.0477 12.0014 45.0864 13.0342C45.0547 14.059 45.229 15.0797 45.599 16.0359C45.969 16.992 46.5271 17.8642 47.2403 18.6007C47.9535 19.3373 48.8073 19.9232 49.751 20.3237C50.6948 20.7242 51.7094 20.9313 52.7346 20.9325C53.9142 20.9309 55.079 20.6693 56.146 20.1665C57.2131 19.6637 58.1562 18.9319 58.9085 18.0233L62.5154 21.2616C61.3513 22.7464 59.8674 23.9496 58.1739 24.7815C56.4805 25.6134 54.6213 26.0526 52.7346 26.0664C51.017 26.088 49.3125 25.7638 47.7227 25.1132C46.1329 24.4626 44.6902 23.4988 43.4805 22.2792C42.2707 21.0597 41.3186 19.6092 40.6809 18.0142C40.0432 16.4192 39.7328 14.7122 39.7682 12.9947C39.7343 11.2814 40.0463 9.57887 40.6856 7.98893C41.3249 6.39899 42.2783 4.95433 43.4888 3.74137C44.6993 2.52841 46.1421 1.57207 47.7307 0.929561C49.3193 0.287053 51.0213 -0.0284211 52.7346 0.00200942V0.00200942Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path d=\"M72.5195 0.449463H77.7851V20.656H87.1314V25.7899H72.5195V0.449463Z\" fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M105.377 0.449463H110.155L120.147 25.7899H114.526L112.933 21.5511H102.823L101.02 25.7899H95.3724L105.377 0.449463ZM111.222 16.9701L107.707 7.82122L104.205 17.0359L111.222 16.9701Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M130.993 17.7597C131.616 18.8039 132.507 19.6616 133.575 20.2429C134.643 20.8242 135.847 21.1078 137.062 21.0638C139.695 21.0638 140.669 19.7474 140.669 18.6154C140.669 16.3775 138.036 15.8246 134.613 14.5872C131.191 13.3498 128.769 11.3489 128.769 7.21546C128.769 2.6476 132.599 0.0806467 137.062 0.0806467C138.66 0.0310009 140.244 0.395159 141.66 1.13781C143.076 1.88047 144.277 2.97642 145.144 4.31941L141.524 7.37342C141.034 6.67528 140.381 6.10682 139.622 5.71698C138.863 5.32715 138.02 5.12762 137.167 5.13557C135.153 5.13557 133.981 6.03071 133.981 7.25495C133.981 9.38749 135.89 9.4928 139.826 11.0593C144.183 12.8496 145.987 15.0085 145.987 18.5364C145.987 23.0121 143.117 26.2372 137.062 26.2372C131.796 26.2372 128.663 23.6703 127.176 20.6557L130.993 17.7597Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M157.966 17.76C158.592 18.8103 159.49 19.6718 160.565 20.2535C161.64 20.8352 162.853 21.1152 164.074 21.0641C166.707 21.0641 167.681 19.7477 167.681 18.6156C167.681 16.3778 165.048 15.8249 161.626 14.5875C158.203 13.3501 155.768 11.3492 155.768 7.21572C155.768 2.64787 159.599 0.080914 164.074 0.080914C165.671 0.0270836 167.255 0.38953 168.67 1.13267C170.084 1.8758 171.282 2.97408 172.144 4.31967L168.497 7.37369C168.007 6.67554 167.354 6.10708 166.595 5.71725C165.836 5.32742 164.993 5.12788 164.14 5.13583C162.113 5.13583 160.941 6.03098 160.941 7.25522C160.941 9.38776 162.863 9.49307 166.799 11.0596C171.156 12.8499 172.96 15.0087 172.96 18.5366C172.96 23.0123 170.09 26.2375 164.035 26.2375C158.769 26.2375 155.623 23.6705 154.135 20.656L157.966 17.76Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path d=\"M183.32 0.449463H188.585V25.7899H183.32V0.449463Z\" fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M212.241 0.00219727C213.941 0.00351283 215.624 0.344431 217.191 1.00495C218.758 1.66546 220.177 2.63227 221.365 3.84864C222.554 5.06501 223.487 6.50644 224.11 8.08836C224.734 9.67027 225.035 11.3608 224.997 13.0607C225.012 16.0494 223.957 18.9447 222.022 21.2223L224.247 23.8551L220.64 26.9881L218.296 24.1974C216.458 25.3724 214.318 25.9897 212.136 25.9745C210.431 25.9832 208.741 25.6543 207.165 25.0067C205.588 24.3592 204.154 23.4058 202.948 22.2016C201.741 20.9974 200.785 19.5662 200.134 17.9905C199.483 16.4149 199.151 14.726 199.156 13.0212C199.194 9.56877 200.587 6.26939 203.035 3.83413C205.482 1.39887 208.788 0.0227052 212.241 0.00219727V0.00219727ZM212.241 21.0644C213.191 21.0612 214.131 20.8688 215.005 20.4983L212.03 16.8124L215.637 13.5741L218.718 17.3785C219.468 16.0644 219.854 14.5739 219.837 13.0607C219.912 12.0234 219.772 10.9817 219.427 10.0007C219.081 9.01972 218.538 8.12041 217.829 7.35891C217.121 6.59741 216.263 5.99007 215.31 5.57477C214.356 5.15948 213.327 4.94515 212.287 4.94515C211.247 4.94515 210.218 5.15948 209.265 5.57477C208.311 5.99007 207.453 6.59741 206.745 7.35891C206.037 8.12041 205.493 9.01972 205.147 10.0007C204.802 10.9817 204.663 12.0234 204.738 13.0607C204.688 14.083 204.845 15.1047 205.198 16.0653C205.551 17.0259 206.094 17.9056 206.794 18.6522C207.494 19.3989 208.337 19.9972 209.272 20.4115C210.208 20.8259 211.218 21.0479 212.241 21.0644Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M21.9044 25.5662C22.5269 25.5441 23.1389 25.3995 23.7054 25.1407C24.272 24.882 24.782 24.514 25.2062 24.058C25.6305 23.602 25.9606 23.0668 26.1779 22.4831C26.3951 21.8993 26.4952 21.2785 26.4723 20.656C26.5043 19.4079 26.0425 18.1976 25.1872 17.2881C24.3319 16.3785 23.1522 15.8433 21.9044 15.7986C21.282 15.8207 20.67 15.9652 20.1034 16.224C19.5369 16.4828 19.0269 16.8507 18.6026 17.3067C18.1784 17.7628 17.8482 18.298 17.631 18.8817C17.4137 19.4654 17.3137 20.0863 17.3366 20.7087C17.3046 21.9568 17.7664 23.1671 18.6217 24.0767C19.477 24.9862 20.6567 25.5215 21.9044 25.5662Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "  <path\n",
    "    d=\"M30.9482 4.80667C30.2036 4.82747 29.4858 5.08876 28.9021 5.55147C28.3183 6.01418 27.9001 6.65344 27.7099 7.37362H13.0585V1.56836H0V15.2983H13.0585V9.493H27.6441C27.8233 10.2296 28.2401 10.8867 28.8303 11.3626C29.4204 11.8385 30.1509 12.1067 30.9087 12.1258C31.8469 12.0847 32.7308 11.674 33.3671 10.9834C34.0035 10.2927 34.3407 9.37833 34.305 8.43989C34.3269 7.51692 33.9889 6.62164 33.3623 5.94353C32.7358 5.26541 31.87 4.8577 30.9482 4.80667Z\"\n",
    "    fill=\"#D7F75B\" />\n",
    "</svg>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf9d16ff",
   "metadata": {},
   "source": [
    "<div style=\"width: 100%; display: flex; justify-content: flex-start; align-items: center; margin-left: 20%;\">\n",
    "    <img src=\"images/classiq-logo.svg\" alt=\"classiq_logo\" width=\"500\" height=\"auto\" style=\"margin-right: 50px;\" />\n",
    "    <img src=\"images/qosf_colour_logo.svg\" alt=\"qosf_logo\" width=\"280\" height=\"auto\" />\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "576d1683-e51c-4fb6-aad6-e221e685cbb7",
   "metadata": {},
   "source": [
    "# Classiq’s Challenge for Quantum Open Source Foundation: Sparse State-Preparation\n",
    "\n",
    "## Brief\n",
    "\n",
    "There are good quantum algorithms for preparing an arbitrary initial quantum state. However, for many applications and quantum algorithms, the state that needs to be prepared is sparse. In such cases, the implementation can be much more efficient, requiring fewer resources like circuit depth and auxiliary qubits. A sparse state has the number of non-zero elements proportional to the number of qubits \\(n\\) (where the total number of possible entries is \\(2^n\\), e.g., a GHZ state). **In this challenge, participants will implement an efficient sparse state preparation algorithm** using the [Classiq platform](https://platform.classiq.io/). The challenge is divided into steps of increasing difficulty, allowing anyone to implement some level of the desired algorithm.\n",
    "\n",
    "The main reference for the challenge is: [An Efficient Algorithm for Sparse Quantum State Preparation paper](https://htor.inf.ethz.ch/publications/img/quantum_dac.pdf).\n",
    "\n",
    "## Explanations\n",
    "\n",
    "State preparation is an elementary building block in quantum computing, pivotal for many quantum algorithms and tasks. These include quantum linear algebra, quantum chemical modeling, quantum search protocols, and quantum machine learning.\n",
    "\n",
    "State preparation involves constructing a quantum state where the amplitudes reflect a specified vector of amplitudes or a predefined function. Mathematically, it is the creation of a state with amplitudes according to a given vector of amplitudes or function:\n",
    "\n",
    "$ |\\psi\\rangle_n = \\sum_{x} a(x)|x\\rangle_n $\n",
    "\n",
    "Creating a state with arbitrary amplitudes often requires resources that scale exponentially with the number of qubits. However, in many practical scenarios, the vector encoding the state's amplitudes remains sparse. This sparsity allows for designing more resource-efficient quantum circuits for state preparation. For example, in quantum machine learning, the amplitudes to be loaded into a quantum state might represent probabilities, and often, only a few of these probabilities are non-zero.\n",
    "\n",
    "## Challenge Definition\n",
    "\n",
    "The task is to load a vector of probabilities into a quantum state such that only a constant number of the probabilities is non-zero. Given a list of indices and their respective probabilities, you will need to create a circuit that loads a state with amplitudes proportional to these probabilities.\n",
    "\n",
    "$ |\\psi\\rangle_n = \\sum_{i} a_i |i\\rangle_n $\n",
    "$ |a_i|^2 = p_i $\n",
    "\n",
    "You have the freedom to load the amplitude with an arbitrary phase.\n",
    "\n",
    "### Example\n",
    "\n",
    "- **Input:**\n",
    "  - Num_qubits: 8 (vector size = 256)\n",
    "  - Probs = {1: 0.25, 17: 0.5, 200: 0.25}\n",
    "\n",
    "- **Possible Loaded State:**\n",
    "  $ |\\psi\\rangle_8 = 0.25|1\\rangle_8 - 0.5|17\\rangle_8 + 0.25|200\\rangle_8 $\n",
    "\n",
    "## Notes\n",
    "\n",
    "You are tasked with creating quantum circuits to prepare specific states. You are permitted to use auxiliary qubits. However, it's essential to ensure that at the circuit's conclusion, there are no residual non-zero or entangled qubits apart from the designated loaded state.\n",
    "\n",
    "There is a spectrum of potential solutions for this task. The efficiency of particular approaches might fluctuate based on problem dimensions. Furthermore, one must navigate trade-offs between multiple circuit parameters: the circuit's depth, the count of auxiliary qubits, gate numbers, and so on.\n",
    "\n",
    "## Submission\n",
    "\n",
    "Submit one .zip folder containing:\n",
    "\n",
    "1. For each target problem:\n",
    "   - The .qmod file.\n",
    "   - The .qprog file.\n",
    "   - The results obtained.\n",
    "   - The Python code used to generate the model (if applicable).\n",
    "   - Explanation of your solution.\n",
    "\n",
    "## Evaluation Criteria\n",
    "\n",
    "1. **Target Problems:** Circuits should be tailored to address the following scenarios (partial solutions will also be reviewed):\n",
    "   - 6 qubits: Probs = {‘000011’: 0.4, ‘111111’: 0.6}\n",
    "   - 10 qubits: Probs = {‘0000000101’: 0.33, ‘0000010001’: 0.33, ‘0001100010’: 0.34}\n",
    "   - 20 qubits: Probs = {‘00000000000000000101’: 0.6, ‘00000000000000010001’: 0.4}\n",
    "2. **Pareto Optimization:** Circuits will be assessed based on a Pareto analysis considering both the circuit depth and the number of used auxiliary qubits. Circuits demonstrating diverse optimizations in this trade-off spectrum will receive extra credit. Multiple circuit submissions for the same problem are welcome.\n",
    "3. **Innovation:** The originality and ingenuity of the solution.\n",
    "4. **Scalability:** How well the solution scales concerning varying parameters like the total number of qubits and the count of non-zero coefficients.\n",
    "\n",
    "Good Luck!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}