{
"cells": [
{
"cell_type": "markdown",
"id": "429e356e",
"metadata": {},
"source": [
"# Boson Sampling\n",
"\n",
"One notable quantum advantage scheme that can be implemented on a photonic quantum computer is the well-known Boson Sampling scheme proposed by Aaronson and Arkhipov . Boson Sampling is a type of photonic quantum computation that starts from Fock basis states and evolves the photonic quantum states by an interferometer. At the end of the Boson Sampling circuit, particle number measurements are carried out to generate samples. Although this setup is theoretically applicable to any bosonic system, the photonic implementation is the most natural. It is generally accepted that Boson Sampling executes a computational task more efficiently than classical computers because solving it requires sampling from the output particle number probability distribution with a randomly chosen interferometer, a challenge considered intractable for classical computation.\n",
"\n",
"In the standard Boson Sampling setup, the input state is typically a Fock basis state $\\ket{ S } = | S_1, S_2, \\ldots S_d \\rangle$, where $n=\\sum_{i=1}^d S_i$ denotes the total number of photons. Although $\\ket{ S }$ can be arbitrary, the values of $S_i$ are typically chosen to be either $1$ or $0$. The photons are then passed through a generic passive linear optical interferometer, characterized by a $d \\times d$ unitary matrix $U$. Since a passive linear circuit preserves the total number of particles, the state vector remains within the $n$-particle subspace of dimension $\\binom{n+d-1}{d-1}$ throughout the entire evolution. Finally, a particle number measurement is performed on each mode, and the probability of obtaining a specific measurement outcome $\\ket{T} = \\ket{T_1, T_2, \\ldots, T_d}$ is given by\n",
"$$\n",
" p(S, T) =\n",
" \\frac{\n",
" |\n",
" \\operatorname{per}\n",
" ( \\operatorname{red}_{T, S} (U) )\n",
" |^2\n",
" }{\n",
" S_1! \\dots S_d! T_1! \\dots T_d!\n",
" },\n",
"$$\n",
"where $\\operatorname{red}_{T, S}$ is the reduction defined as repeating the rows and columns according to $T$ and $S$, respectively. $U$ is the unitary matrix corresponding to the passive linear circuit, and the permanent $\\operatorname{per}$ of a matrix is defined via\n",
"$$\n",
" \\operatorname{per}(A) = \\sum_{\\sigma \\in S_n} \\prod_{i = 1}^n A_{\\sigma(i), i}, \\qquad A \\in \\mathbb{C}^{n \\times n}.\n",
"$$\n",
"Most importantly, the permanent is the source of the widely accepted classical intractability of the Boson Sampling problem: given a general matrix $A \\in \\mathbb{C}^{n \\times n}$ even approximating $\\operatorname{per}(A)$ is $\\#P$-complete, and finding a polynomial-time algorithm for calculating this would imply P = NP ."
]
},
{
"cell_type": "markdown",
"id": "31102a63",
"metadata": {},
"source": [
"If you want to run the Boson Sampling algorithm in Piquasso, it is easy to do by using [SamplingSimulator](../simulators/sampling.rst#piquasso._simulators.sampling.simulator.SamplingSimulator) with the [Interferometer](../instructions/gates.rst#piquasso.instructions.gates.Interferometer) instruction. A simple example is given as follows:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "1d5b9e46",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[(1, 0, 0, 0, 1, 1, 0), (0, 1, 0, 0, 2, 0, 0), (1, 0, 1, 0, 1, 0, 0), (0, 0, 2, 0, 1, 0, 0), (0, 1, 0, 1, 0, 0, 1), (0, 1, 0, 2, 0, 0, 0), (0, 0, 0, 1, 0, 0, 2), (0, 0, 1, 0, 0, 1, 1), (1, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, 1, 1, 0), (0, 1, 0, 0, 1, 1, 0), (0, 0, 0, 2, 0, 0, 1), (0, 1, 0, 0, 1, 1, 0), (0, 0, 0, 0, 3, 0, 0), (0, 1, 0, 0, 0, 2, 0), (0, 0, 2, 0, 0, 0, 1), (0, 1, 0, 0, 1, 0, 1), (0, 0, 0, 2, 1, 0, 0), (0, 0, 0, 1, 2, 0, 0), (0, 0, 0, 2, 0, 0, 1)]\n"
]
}
],
"source": [
"import piquasso as pq\n",
"\n",
"from scipy.stats import unitary_group\n",
"\n",
"d = 7\n",
"\n",
"interferometer_matrix = unitary_group.rvs(d)\n",
"\n",
"with pq.Program() as program:\n",
" pq.Q(all) | pq.StateVector([1, 1, 1, 0, 0, 0, 0])\n",
"\n",
" pq.Q(all) | pq.Interferometer(interferometer_matrix)\n",
"\n",
" pq.Q(all) | pq.ParticleNumberMeasurement()\n",
"\n",
"simulator = pq.SamplingSimulator(d=d)\n",
"\n",
"result = simulator.execute(program, shots=20)\n",
"\n",
"print(result.samples)"
]
},
{
"cell_type": "markdown",
"id": "4213eccc",
"metadata": {},
"source": [
"If you want to execute lossy Boson Sampling, you can do this by using the [Loss](../instructions/channels.rst#piquasso.instructions.channels.Loss) channel:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "f350e630",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[(0, 0, 0, 2, 0, 0, 1), (0, 1, 1, 0, 0, 0, 1), (0, 1, 0, 0, 0, 2, 0), (1, 0, 0, 0, 2, 0, 0), (0, 0, 0, 1, 0, 0, 0), (0, 0, 0, 0, 1, 1, 0), (0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, 2, 0, 0), (0, 2, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, 1, 0), (0, 0, 2, 0, 0, 1, 0), (0, 0, 0, 1, 1, 1, 0), (1, 0, 0, 0, 0, 1, 1), (0, 2, 0, 0, 1, 0, 0), (0, 0, 1, 1, 0, 1, 0), (0, 0, 0, 0, 0, 2, 0), (0, 1, 1, 0, 1, 0, 0), (0, 0, 0, 1, 2, 0, 0), (0, 0, 1, 0, 0, 0, 1), (0, 0, 0, 0, 0, 0, 1)]\n"
]
}
],
"source": [
"transmissivity = 0.9\n",
"\n",
"with pq.Program() as program:\n",
" pq.Q(all) | pq.StateVector([1, 1, 1, 0, 0, 0, 0])\n",
"\n",
" pq.Q(all) | pq.Interferometer(interferometer_matrix)\n",
"\n",
" for i in range(d):\n",
" pq.Q(i) | pq.Loss(transmissivity)\n",
"\n",
" pq.Q(all) | pq.ParticleNumberMeasurement()\n",
"\n",
"result = simulator.execute(program, shots=20)\n",
"\n",
"print(result.samples)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": ".venv",
"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.16"
}
},
"nbformat": 4,
"nbformat_minor": 5
}