{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "TpUfmA4yJDgy" }, "source": [ "##### Copyright 2020 The Cirq Developers" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "cellView": "form", "execution": { "iopub.execute_input": "2024-08-16T10:47:44.661229Z", "iopub.status.busy": "2024-08-16T10:47:44.660705Z", "iopub.status.idle": "2024-08-16T10:47:44.664830Z", "shell.execute_reply": "2024-08-16T10:47:44.664194Z" }, "id": "XUWPbFGCJGLH" }, "outputs": [], "source": [ "#@title Licensed under the Apache License, Version 2.0 (the \"License\");\n", "# you may not use this file except in compliance with the License.\n", "# You may obtain a copy of the License at\n", "#\n", "# https://www.apache.org/licenses/LICENSE-2.0\n", "#\n", "# Unless required by applicable law or agreed to in writing, software\n", "# distributed under the License is distributed on an \"AS IS\" BASIS,\n", "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n", "# See the License for the specific language governing permissions and\n", "# limitations under the License." ] }, { "cell_type": "markdown", "metadata": { "id": "zpY-JW-nJLhW" }, "source": [ "# Hidden linear function problem" ] }, { "cell_type": "markdown", "metadata": { "id": "wsWh_7cRJM7E" }, "source": [ "\n", " \n", " \n", " \n", " \n", "
\n", " View on QuantumAI\n", " \n", " Run in Google Colab\n", " \n", " View source on GitHub\n", " \n", " Download notebook\n", "
" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:47:44.668159Z", "iopub.status.busy": "2024-08-16T10:47:44.667734Z", "iopub.status.idle": "2024-08-16T10:48:00.200604Z", "shell.execute_reply": "2024-08-16T10:48:00.199515Z" }, "id": "bd9529db1c0b" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "installing cirq...\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "\u001b[31mERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.\r\n", "tensorflow-metadata 1.15.0 requires protobuf<4.21,>=3.20.3; python_version < \"3.11\", but you have protobuf 4.25.4 which is incompatible.\u001b[0m\u001b[31m\r\n", "\u001b[0m" ] }, { "name": "stdout", "output_type": "stream", "text": [ "installed cirq.\n" ] } ], "source": [ "try:\n", " import cirq\n", "except ImportError:\n", " print(\"installing cirq...\")\n", " !pip install --quiet cirq\n", " print(\"installed cirq.\")" ] }, { "cell_type": "markdown", "metadata": { "id": "f215459c3180" }, "source": [ "In this notebook we consider a problem from the paper \"[Quantum advantage with shallow circuits](https://arxiv.org/abs/1704.00690)\" and build a quantum circuit, which solves it, in Cirq. " ] }, { "cell_type": "markdown", "metadata": { "id": "d06fbc8d03f1" }, "source": [ "## Introduction\n", "\n", "It's well-known that some problems can be solved on the quantum computer exponentially faster than on the classical one in terms of computation time. However, there is more subtle way in which quantum computers are more powerful. There is a problem, which can be solved by quantum circuit of constant depth, but can't be solved by classical circuit of constant depth. In this notebook we will consider this problem.\n", "\n", "\n", "### Structure of this notebook\n", "\n", "We start by giving formal statement of the problem. Then we solve this problem in a straightforward way, which follows directly from the problem definition. We will use this solution to verify our quantum solution in the next part. Also, this part contains helper code to generate \"interesting\" instances of the problem.\n", "\n", "In the next part we solve this problem with Cirq. First, we write a code which builds a quantum circuit for solving arbitrary instances of the problem. Then we use Cirq's Clifford simulator to simulate this circuit. We do it for small instances and compare results to the brute force solution from the previous part. Then, we solve the problem for a larger instance of the problem to demonstrate that it can be solved efficiently.\n", "\n", "Goal of this notebook is to introduce the reader to the problem and to show how Cirq can be used to solve it. We don't include proofs, but we refer the reader to corresponding lemmas in the original paper." ] }, { "cell_type": "markdown", "metadata": { "id": "f9af5c33557b" }, "source": [ "## Problem statement\n", "\n", "In this problem we consider a [quadratic form](https://en.wikipedia.org/wiki/Quadratic_form) of a [binary vector](https://en.wikipedia.org/wiki/Bit_array) and with binary coefficients (but additions and multiplications are evaluated modulo 4). Then we restrict this quadratic form, i.e. we allow to use only certain binary vectors as input. It turns out that under this restriction this quadratic form is equivalent to a linear function, i.e. it just evaluates dot product of input vector and certain scalar vector. Task is to find this scalar vector.\n", "\n", "In other words, we have a linear function, which is \"hidden\" inside a quadratic form.\n", "\n", "### Formal statement of the problem\n", "\n", "Consider $A \\in \\mathbb{F}_2^{n \\times n}$ - upper-triangular binary matrix of size $n \\times n$, $b \\in \\mathbb{F}_2^n$ - binary vector of length $n$.\n", "\n", "Define a function $q : \\mathbb{F}_2^n \\to \\mathbb{Z}_4$:\n", "\n", "$$q(x) = (2 x^T A x + b^T x) ~\\text{mod}~ 4 = \\left(2 \\sum_{i,j}A_{i,j}x_i x_j + \\sum_{i} b_i x_i \\right) ~\\text{mod}~ 4 , $$ \n", "\n", "Also define\n", "\n", "$$\\mathcal{L}_q = \\Big\\{x \\in \\mathbb{F}_2^n : q(x \\oplus y) = (q(x) + q(y)) ~\\text{mod}~ 4 ~~ \\forall y \\in \\mathbb{F}_2^n \\Big\\}.$$\n", "\n", "Turns out (see Lemma 1 on page 6 in [1]) that restriction of $q$ on $\\mathcal{L}_q$ is a linear function, i.e. there exists such $z \\in \\mathbb{F}_2^n$, that\n", "\n", "$$q(x) = 2 z^T x ~~\\forall x \\in \\mathcal{L}_q.$$\n", "\n", "Our task is, given $A$ and $b$, to find $z$. There may be multiple answers - we need to find any such answer.\n", "\n", "**Notation in the problem**\n", "\n", "* $q$ - quadratic form; $A$ - matrix of its quadratic coefficients; $b$ - vector of its linear coefficients;\n", "* $\\mathcal{L}_q$ - linear space on which we restrict $q(x)$ in order to get linear function;\n", "* $z$ - vector of coefficients of the linear function we get by restricting $q$ on $\\mathcal{L}_q$. This vector is \"hidden\" in the coefficients of $q$ and the problem is to find it.\n", "\n", "### Why is this problem interesting?\n", "\n", "#### 1. It's a problem without an oracle\n", "\n", "There are other problems where task is to find coefficients of a linear function. But usually the linear function is represented by an [oracle](https://en.wikipedia.org/wiki/Oracle_machine). See, for example, [Bernstein–Vazirani algorithm](https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm).\n", "\n", "In this problem we avoid use of an oracle by \"hiding\" the linear function in the coefficients of quadratic form $A$ and $b$, which are the only inputs to the problem.\n", "\n", "#### 2. Quantum circuits have advantage over classical when solving this problem\n", "\n", "As we will show below, this problem can be solved with a Clifford circuit. Therefore, according to the [Gottesman–Knill theorem](https://en.wikipedia.org/wiki/Gottesman%E2%80%93Knill_theorem), this problem can be solved in polynomial time on a classical computer. So, it might look like quantum computers aren't better than classical ones in solving this problem.\n", "\n", "However, if we apply certain restrictions on matrix $A$, the circuit will have fixed depth (i.e. number of `Moment`s). Namely, if the matrix $A$ is an adjacency matrix of a \"grid\" graph (whose edges can be colored in 4 colors), all CZ gates will fit in 4 `Moment`s, and overall we will have only 8 `Moment`s - and this doesn't depend on $n$.\n", "\n", "But for classical circuits it can be proven (see [1]) that even if we restrict matrix $A$ in the same way, the depth of classical circuit (with gates of bounded fan-in) must grow as $n$ grows (in fact, it grows as $\\log(n)$).\n", "\n", "In terms of complexity theory, this problem is in [QNC0](https://complexityzoo.net/Complexity_Zoo:Q#qnc0), but not in [NC0](https://en.wikipedia.org/wiki/NC_(complexity)), which shows that\n", "QNC0 $\\nsubseteq$ NC0.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "b8ee33969ed8" }, "source": [ "## Preparation and brute force solution\n", "\n", "For small values of $n$ we can solve this problem with a trivial brute force solution. First, we need to build $\\mathcal{L}_q$. We can do that by checking for all possible $2^n$ binary vectors, whether it belongs to $\\mathcal{L}_q$, using the definition of $\\mathcal{L}_q$. Then we need to try all possible $z \\in \\mathbb{F}_2^n$, and for each of them and for each $x \\in \\mathcal{L}_q$ check whether $q(x) = 2 z^T x$.\n", "\n", "Below we implement a class which represents an instance of a problem and solves it with a brute force solution." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:00.205030Z", "iopub.status.busy": "2024-08-16T10:48:00.204708Z", "iopub.status.idle": "2024-08-16T10:48:01.962817Z", "shell.execute_reply": "2024-08-16T10:48:01.961888Z" }, "id": "870e96816f9a" }, "outputs": [], "source": [ "import numpy as np\n", "import cirq" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:01.967080Z", "iopub.status.busy": "2024-08-16T10:48:01.966312Z", "iopub.status.idle": "2024-08-16T10:48:01.976377Z", "shell.execute_reply": "2024-08-16T10:48:01.975509Z" }, "id": "cfe6ae6e8f61" }, "outputs": [], "source": [ "class HiddenLinearFunctionProblem:\n", " \"\"\"Instance of Hidden Linear Function problem.\n", " \n", " The problem is defined by matrix A and vector b, which are\n", " the coefficients of quadratic form, in which linear function\n", " is \"hidden\".\n", " \"\"\"\n", " def __init__(self, A, b):\n", " self.n = A.shape[0]\n", " assert A.shape == (self.n, self.n)\n", " assert b.shape == (self.n, )\n", " for i in range(self.n):\n", " for j in range(i+1):\n", " assert A[i][j] == 0, 'A[i][j] can be 1 only if i>i) % 2 for i in range(self.n)]) for m in range(2**self.n)]\n", "\n", " def vector_in_L(x):\n", " for y in all_vectors:\n", " if self.q( (x + y)%2 ) != (self.q(x) + self.q(y))%4:\n", " return False\n", " return True\n", "\n", " # L is subspace to which we restrict domain of quadratic form.\n", " # Corresponds to `L_q` in the problem definition.\n", " self.L = [x for x in all_vectors if vector_in_L(x)]\n", " \n", " # All vectors `z` which are solutions to the problem.\n", " self.all_zs = [z for z in all_vectors if self.is_z(z)]\n", " \n", " def is_z(self, z):\n", " \"\"\"Checks by definition, whether given vector `z` is solution to this problem.\"\"\"\n", " assert z.shape == (self.n, )\n", " assert self.L is not None\n", " for x in self.L:\n", " if self.q(x) != 2 * ((z @ x) % 2):\n", " return False\n", " return True" ] }, { "cell_type": "markdown", "metadata": { "id": "e9a0d26956ec" }, "source": [ "For testing, we need to generate an instance of a problem. We can generate random $A$ and $b$. However, for some $A$ and $b$ problem is trivial - that is, $\\mathcal{L}_q = \\{0\\}$ and therefore any $z$ is a solution. In fact, product of $|\\mathcal{L}_q|$ and number of solutions is always equal to $2^n$ (see Lemma 2 in [1]), so we want a problem with large $\\mathcal{L}_q$.\n", "\n", "Code below can be used to generate random problem with given size of $\\mathcal{L}_q$." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:01.980030Z", "iopub.status.busy": "2024-08-16T10:48:01.979414Z", "iopub.status.idle": "2024-08-16T10:48:03.326382Z", "shell.execute_reply": "2024-08-16T10:48:03.325608Z" }, "id": "97f790af7048" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Size of subspace L: 4\n", "Number of solutions: 256\n" ] } ], "source": [ "def random_problem(n, seed=None):\n", " \"\"\"Generates instance of the problem with given `n`.\n", " \n", " Args:\n", " n: dimension of the problem.\n", " \"\"\"\n", " if seed is not None:\n", " np.random.seed(seed) \n", " A = np.random.randint(0, 2, size=(n,n))\n", " for i in range(n):\n", " for j in range(i+1):\n", " A[i][j] = 0\n", " b = np.random.randint(0, 2, size=n)\n", " problem = HiddenLinearFunctionProblem(A, b)\n", " return problem\n", " \n", "def find_interesting_problem(n, min_L_size):\n", " \"\"\"Generates \"interesting\" instance of the problem.\n", " \n", " Returns instance of problem with given `n`, such that size of \n", " subspace `L_q` is at least `min_L_size`.\n", " \n", " Args:\n", " n: dimension of the problem.\n", " min_L_size: minimal cardinality of subspace L.\n", " \"\"\"\n", " for _ in range(1000):\n", " problem = random_problem(n)\n", " problem.bruteforce_solve()\n", " if len(problem.L) >= min_L_size and not np.max(problem.A) == 0:\n", " return problem\n", " return None\n", "\n", "problem = find_interesting_problem(10, 4)\n", "print(\"Size of subspace L: %d\" % len(problem.L))\n", "print(\"Number of solutions: %d\" % len(problem.all_zs))" ] }, { "cell_type": "markdown", "metadata": { "id": "57e6a2a38247" }, "source": [ "We ran this function for a while and found an instance with $n=10$ and $|\\mathcal{L}_q|=16$, so only 64 of 1024 possible vectors are solutions. So, chance of randomly guessing a solution is $\\frac{1}{16}$. We define this instance below by values of $A$ and $b$ and we will use it later to verify our quantum solution." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:03.330209Z", "iopub.status.busy": "2024-08-16T10:48:03.329620Z", "iopub.status.idle": "2024-08-16T10:48:03.699731Z", "shell.execute_reply": "2024-08-16T10:48:03.698981Z" }, "id": "d1e086be9248" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Size of subspace L: 16\n", "Number of solutions: 64\n" ] } ], "source": [ "A = np.array([[0, 1, 1, 0, 0, 1, 0, 0, 1, 1],\n", " [0, 0, 0, 1, 1, 1, 1, 1, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 1, 1, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n", " [0, 0, 0, 0, 0, 1, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 1, 1, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n", " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])\n", "b = np.array([0, 0, 0, 0, 1, 1, 1, 0, 0, 1])\n", "problem_10_64 = HiddenLinearFunctionProblem(A, b)\n", "problem_10_64.bruteforce_solve()\n", "print(\"Size of subspace L: %d\" % len(problem_10_64.L))\n", "print(\"Number of solutions: %d\" % len(problem_10_64.all_zs))" ] }, { "cell_type": "markdown", "metadata": { "id": "a32f20d45d05" }, "source": [ "## Solution with a quantum circuit" ] }, { "cell_type": "markdown", "metadata": { "id": "bf9d950a5c2e" }, "source": [ "As shown in [1], given problem can be solved by a quantum circuit, which implements operator $H ^ {\\otimes n} U_q H ^ {\\otimes n}$, where\n", "\n", "$$U_q = \\prod_{1 < i < j < n} CZ_{ij}^{A_{ij}} \\cdot \\bigotimes_{j=1}^{n} S_j^{b_j} .$$\n", "\n", "We need to apply this operator to $| 0^n \\rangle$ and measure the result - result is guaranteed to be one of the solutions. Moreover, we can get any solution with equal probability. \n", "\n", "**Why does this circuit solve the problem?** Define $p(z) = \\left| \\langle z | H ^ {\\otimes n} U_q H ^ {\\otimes n} | 0^n \\rangle \\right|^2$. It can be shown that $p(z)>0$ iff $z$ is a solution. For the proof, see Lemma 2 on page 7 in [1].\n", "\n", "Let's generate such a circuit and simulate it.\n", "\n", "Note that: \n", "\n", "* We use `Cirq.S` gate, whose matrix is $\\left(\\begin{smallmatrix}1 & 0\\\\0 & i\\end{smallmatrix}\\right)$. In the paper [1] matrix of S gate is defined as $\\left(\\begin{smallmatrix}1 & 0\\\\0 & -i\\end{smallmatrix}\\right)$. But for this problem it doesn't matter.\n", "\n", "* We reorder CZ gates in such a way so they take less moments. This is a problem of minimal [edge coloring](https://en.wikipedia.org/wiki/Edge_coloring), and we solve it here with a simple greedy algorithm (there are better algorithms, but finding true optimum is not the point here). We can do that because CZ gates commute (because their matrices are diagonal). This part is not essential to the solution - it just makes the circuit shorter.\n", "\n", "* All gates are Clifford gates, so we can use Clifford simulator." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:03.703623Z", "iopub.status.busy": "2024-08-16T10:48:03.702990Z", "iopub.status.idle": "2024-08-16T10:48:03.708434Z", "shell.execute_reply": "2024-08-16T10:48:03.707770Z" }, "id": "5b072640193e" }, "outputs": [], "source": [ "def edge_coloring(A):\n", " \"\"\"Solves edge coloring problem.\n", " \n", " Args:\n", " A: adjacency matrix of a graph.\n", " \n", " Returns list of lists of edges, such as edges in each list \n", " do not have common vertex. \n", " Tries to minimize length of this list.\n", " \"\"\"\n", " A = np.copy(A)\n", " n = A.shape[0]\n", " ans = []\n", " while np.max(A) != 0:\n", " edges_group = []\n", " used = np.zeros(n, dtype=bool)\n", " for i in range(n):\n", " for j in range(n):\n", " if A[i][j] == 1 and not used[i] and not used[j]:\n", " edges_group.append((i, j))\n", " A[i][j] = 0\n", " used[i] = used[j] = True\n", " ans.append(edges_group)\n", " return ans" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:03.711811Z", "iopub.status.busy": "2024-08-16T10:48:03.711190Z", "iopub.status.idle": "2024-08-16T10:48:03.750223Z", "shell.execute_reply": "2024-08-16T10:48:03.749493Z" }, "id": "48a0723c242c" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " ┌───┐ ┌──┐ ┌───┐ ┌───┐ ┌───┐\n", "0: ───H────@───────@──────@───────@───────@──────────────────────H───M('0')───\n", " │ │ │ │ │\n", "1: ───H────@───────┼@─────┼@──────┼@──────┼@─────@───@───@───────H───M('1')───\n", " ││ ││ ││ ││ │ │ │\n", "2: ───H────@───────@┼─────┼┼@─────┼┼@─────┼┼─────┼───┼───┼───────H───M('2')───\n", " │ │ │││ │││ ││ │ │ │\n", "3: ───H────┼@───────@─────┼┼┼─────┼┼┼─────┼┼─────┼───┼───┼───────H───M('3')───\n", " ││ │││ │││ ││ │ │ │\n", "4: ───H────┼┼@─────@──────┼@┼─────┼┼┼─────┼┼─────┼───┼───┼───S───H───M('4')───\n", " │││ │ │ │ │││ ││ │ │ │\n", "5: ───H────┼┼@─────┼@─────@─┼─────┼@┼─────┼┼@────┼───┼───┼───S───H───M('5')───\n", " ││ ││ │ │ │ │││ │ │ │\n", "6: ───H────@┼──────┼@─────@─┼─────┼─┼─────┼@┼────┼───┼───┼───S───H───M('6')───\n", " │ │ │ │ │ │ │ │ │ │ │\n", "7: ───H────@┼──────┼@─────┼─@─────┼─┼─────┼─@────@───┼───┼───────H───M('7')───\n", " ││ ││ │ │ │ │ │ │\n", "8: ───H────┼@──────┼@─────┼───────@─┼─────┼──────────@───┼───────H───M('8')───\n", " │ │ │ │ │ │\n", "9: ───H────@───────@──────@─────────@─────@──────────────@───S───H───M('9')───\n", " └───┘ └──┘ └───┘ └───┘ └───┘\n" ] }, { "data": { "text/plain": [ "array([1, 0, 0, 0, 0, 0, 0, 1, 1, 0], dtype=uint8)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def generate_circuit_for_problem(problem):\n", " \"\"\"Generates `cirq.Circuit` which solves instance of Hidden Linear Function problem.\"\"\"\n", " \n", " qubits = cirq.LineQubit.range(problem.n)\n", " circuit = cirq.Circuit()\n", " \n", " # Hadamard gates at the beginning (creating equal superposition of all states).\n", " circuit += cirq.Moment([cirq.H(q) for q in qubits])\n", " \n", " # Controlled-Z gates encoding the matrix A.\n", " for layer in edge_coloring(problem.A):\n", " for i, j in layer:\n", " circuit += cirq.CZ(qubits[i], qubits[j])\n", " \n", " # S gates encoding the vector b.\n", " circuit += cirq.Moment([cirq.S.on(qubits[i]) for i in range(problem.n) if problem.b[i] == 1])\n", " \n", " # Hadamard gates at the end.\n", " circuit += cirq.Moment([cirq.H(q) for q in qubits])\n", " \n", " # Measurements.\n", " circuit += cirq.Moment([cirq.measure(qubits[i], key=str(i)) for i in range(problem.n)]) \n", " \n", " return circuit\n", "\n", "def solve_problem(problem, print_circuit=False):\n", " \"\"\"Solves instance of Hidden Linear Function problem.\n", " \n", " Builds quantum circuit for given problem and simulates\n", " it with the Clifford simulator. \n", " \n", " Returns measurement result as binary vector, which is\n", " guaranteed to be a solution to given problem.\n", " \"\"\"\n", " circuit = generate_circuit_for_problem(problem)\n", " \n", " if print_circuit:\n", " print(circuit)\n", " \n", " sim = cirq.CliffordSimulator()\n", " result = sim.simulate(circuit)\n", " z = np.array([result.measurements[str(i)][0] for i in range(problem.n)])\n", " return z\n", "\n", "solve_problem(problem_10_64, print_circuit=True)" ] }, { "cell_type": "markdown", "metadata": { "id": "52f1706a22e0" }, "source": [ "## Testing\n", "\n", "Now, let's test this algorithm. Let's solve it with a quantum circuit 100 times and each time check that measurement result is indeed an answer to the problem." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:03.753610Z", "iopub.status.busy": "2024-08-16T10:48:03.753088Z", "iopub.status.idle": "2024-08-16T10:48:04.695666Z", "shell.execute_reply": "2024-08-16T10:48:04.694922Z" }, "id": "acf7c42029f3" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OK\n" ] } ], "source": [ "def test_problem(problem):\n", " problem.bruteforce_solve()\n", " tries = 100\n", " for _ in range(tries):\n", " z = solve_problem(problem)\n", " assert problem.is_z(z)\n", " \n", "test_problem(problem_10_64)\n", "print('OK')" ] }, { "cell_type": "markdown", "metadata": { "id": "b5b59dfac1e6" }, "source": [ "Let's repeat that for 10 other problems with $n=8$ and chance of random guessing at most $\\frac{1}{4}$." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:04.699699Z", "iopub.status.busy": "2024-08-16T10:48:04.699047Z", "iopub.status.idle": "2024-08-16T10:48:11.288036Z", "shell.execute_reply": "2024-08-16T10:48:11.287266Z" }, "id": "29eced5be274" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OK\n" ] } ], "source": [ "for _ in range(10):\n", " test_problem(find_interesting_problem(8, 4))\n", "print('OK')" ] }, { "cell_type": "markdown", "metadata": { "id": "d19658dcebd9" }, "source": [ "Now, let's run our algorithm on a problem with $n=200$." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2024-08-16T10:48:11.291671Z", "iopub.status.busy": "2024-08-16T10:48:11.291388Z", "iopub.status.idle": "2024-08-16T10:48:14.008835Z", "shell.execute_reply": "2024-08-16T10:48:14.008131Z" }, "id": "621543d134cc" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 2.7 s, sys: 15.7 ms, total: 2.71 s\n", "Wall time: 2.71 s\n" ] }, { "data": { "text/plain": [ "array([1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1,\n", " 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1,\n", " 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1,\n", " 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0,\n", " 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,\n", " 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1,\n", " 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\n", " 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,\n", " 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,\n", " 1, 0], dtype=uint8)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "tries = 200\n", "problem = random_problem(tries, seed=0)\n", "solve_problem(problem, print_circuit=False)" ] }, { "cell_type": "markdown", "metadata": { "id": "bfe32efba9ab" }, "source": [ "## References\n", "\n", "[1] [Quantum advantage with shallow circuits](https://arxiv.org/abs/1704.00690) by Sergey Bravyi, David Gosset and Robert König." ] } ], "metadata": { "colab": { "name": "hidden_linear_function.ipynb", "toc_visible": true }, "kernelspec": { "display_name": "Python 3", "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.14" } }, "nbformat": 4, "nbformat_minor": 0 }