---
abstract: 'A fundamental model of quantum computation is the programmable quantum gate array. This is a quantum processor which is fed by a program state that induces a corresponding quantum operation on input states. While being programmable, any finite-dimensional design of this model is known to be non-universal, meaning that the processor cannot perfectly simulate an arbitrary quantum channel over the input. Characterizing how close the simulation is and finding the optimal program state have been open questions in the last 20 years. Here we answer these questions by showing that the search of the optimal program state is a convex optimization problem that can be solved via semidefinite programming and gradient-based machine learning methods. We apply this general result to different types of processors, from a shallow design based on quantum teleportation, to deeper schemes relying on port-based teleportation and parametric quantum circuits.'
author:
- Leonardo Banchi
- Jason Pereira
- Seth Lloyd
- Stefano Pirandola
bibliography:
- 'biblio.bib'
title: Convex optimization of programmable quantum computers
---

*Introduction*.– Back in 1997 a seminal work by Nielsen and Chuang [@nielsen1997programmable] proposed a quantum version of the programmable gate array that has become a fundamental model for quantum computation [@nielsen2000quantum]. This is a quantum processor where a fixed quantum operation is applied to an input state together with a program state. The aim of the program state is to induce the processor to apply some target quantum gate or channel [@watrous2018theory] to the input state. Such a desired feature of quantum programmability comes with a cost: The model cannot be universal, unless the program state is allowed to have an infinite dimension, i.e., infinite qubits [@nielsen1997programmable; @knill2001scheme]. Even though this limitation has been known for many years, there is still no exact characterization on how well a finite-dimensional programmable quantum processor can generate or simulate an arbitrary quantum channel. Also there is no literature on how to find the corresponding optimal program state or even to show that this state can indeed be found by some optimization procedure. Here we show the solutions to these long-standing open problems.

In this work we show that the optimization of programmable quantum computers is a convex problem where the solution can always be found by means of classical semidefinite programming (SDP) and classical gradient-based machine learning (ML) methods. More precisely, we consider the cost function corresponding to the diamond distance [@kitaev2002classical; @watrous2018theory] between a target quantum channel and its simulation via the quantum processor. We then show that the cost minimization becomes a convex problem in the space of the program states, so that we can always find the best channel simulation and the optimal program state.

The optimization is particularly efficient for shallow designs where the operation of the quantum processor is based on teleportation or port-based teleportation (PBT) [@ishizaka2008asymptotic; @ishizaka2009quantum; @ishizaka2015some] with small number of ports. For deeper architectures, e.g., PBT processors with many ports and processors based on parametric quantum circuits (PQCs) [@lloyd1996universal] we show alternative procedures based on the minimization of other cost functions (trace distance and quantum fidelity) by means of the projected subgradient method [@boyd2003subgradient] and the conjugate gradient method [@jaggi2011convex; @jaggi2013revisiting]. The performances of the various programmable processors are benchmarked towards the simulation of qubit rotations and amplitude damping channels.

*Programmable quantum computing*.– Let us consider an arbitrary quantum channel $\mathcal{E}$ mapping $d$-dimensional input states into $d^{\prime}$-dimensional output states, where $d^{\prime}\neq d$ in the general case. This channel may represent the overall action of a quantum computation and does not need to be a unitary transformation. Let us simulate $\mathcal{E}$ by means of a programmable quantum processor. In general, this processor can be modeled by a fixed completely positive trace-preserving (CPTP) map $Q$ which is be applied to both the input state and a variable program state $\pi$. In this way, the processor transforms the input state by means of an approximate channel $\mathcal{E}_{\pi}$ as $$\mathcal{E}_{\pi}(\rho)=\mathrm{Tr}_{2}\left[  Q(\rho\otimes\pi)\right]
.\label{channelDEF}$$ The open problem is to determine the optimal program state $\tilde{\pi}$ minimizing the cost function $$C_{\diamond}(\pi):=\left\Vert \mathcal{E}-\mathcal{E}_{\pi}\right\Vert
_{\diamond},\label{Cdiamond}$$ in terms of the diamond distance [@kitaev2002classical; @watrous2018theory] between the target channel $\mathcal{E}$ and its simulation $\mathcal{E}_{\pi
}$. Recall that the diamond distance is defined by $\left\Vert \mathcal{E}-\mathcal{E}_{\pi}\right\Vert _{\diamond}:=\max_{\varphi}\left\Vert
\mathcal{I}\otimes\mathcal{E}(\varphi)-\mathcal{I}\otimes\mathcal{E}_{\pi
}(\varphi)\right\Vert _{1}$, where $\mathcal{I}$ is the identity map and $\left\Vert O\right\Vert _{1}:=\mathrm{Tr}\sqrt{O^{\dagger}O}$ is the trace norm [@nielsen2000quantum].

It is important to note that this problem can be reduced to a simpler one by introducing the channel’s Choi matrix $\chi_{\mathcal{E}}:=\mathcal{I}\otimes\mathcal{E}(\Phi)$, where $\Phi:=\left\vert \Phi\right\rangle\!
\left\langle \Phi\right\vert $ is a $d$-dimensional maximally-entangled state. In fact, we may also write the Choi matrix $\chi_{\pi}:=\chi_{\mathcal{E}_{\pi}}$ of the simulated channel $\mathcal{E}_{\pi}$ and note that this matrix is linear in the program state $\pi$. In other words, we have $\chi_{\pi}=\Lambda(\pi)$, where $\Lambda$ is a CPTP map from the program $\pi$ to $\chi_{\pi}$ and fully describes the action of the processor $Q$ (see also Fig. \[progP\]). Then, using results from Refs. [@watrous2018theory; @Karol; @fuchs1999cryptographic], we may write $$C_{\diamond}(\pi)\leq d~C_{1}(\pi)\leq2d\sqrt{C_{F}(\pi)},$$ where $C_{1}(\pi):=\left\Vert \chi_{\mathcal{E}}-\chi_{\pi}\right\Vert _{1}$ is the trace distance [@nielsen2000quantum] between target and simulated Choi matrices, and $C_{F}(\pi)=1-F(\pi)^{2}$ where $F(\pi):=\left\Vert
\sqrt{\chi_{\mathcal{E}}}\sqrt{\chi_{\pi}}\right\Vert _{1}$ is their fidelity.

![Quantum processor $Q$ with program state $\pi$ which simulates a quantum channel $\mathcal{E}_{\pi}$ from input to output. We also show the CPTP map $\Lambda$ of the processor, from the program state $\pi$ to the output Choi matrix $\chi_{\pi}$ (generated by partial transmission of the maximally-entangled state $\Phi$).[]{data-label="progP"}](progP.pdf){width="40.00000%"}

*Convex optimization*.– One of the main problems in the optimization of reconfigurable quantum chips is that the relevant cost functions are not convex in the set of classical parameters. This problem is completely solved here thanks to the fact that the optimization of a programmable quantum processor is done with respect to a quantum state. In fact, we may prove the following.

\[t:convexC1CF\] Consider the simulation of a target quantum channel $\mathcal{E}$ by means of a programmable quantum processor $Q$. The optimization of the cost functions $C_{\diamond}$, $C_{1}$ or $C_{F}$ is a convex problem in the space of program states $\pi$. In particular, the global minimum $\tilde{\pi}$ for $C_{\diamond}$ can always be found as a local minimum via SDP.

This convexity result is generally valid for any cost function which is convex in $\pi$. This is the case for any desired norm, not only the trace norm, but also the Frobenius norm, or any Schatten p-norm. It also applies to the relative entropy. Furtheremore, the result can also be extended to any convex parametrization of the program states. The full proof of this theorem is given in the companion paper [@PRAlong]. Here we only show the proof for $C_{\diamond}(\pi)$. In fact, we may write $$\begin{gathered}
C_{\diamond}[p\pi+(1-p)\pi^{\prime}]:=\left\Vert \mathcal{E}-\mathcal{E}_{p\pi+(1-p)\pi^{\prime}}\right\Vert _{\diamond}\nonumber\\
\overset{(1)}{=}\left\Vert (p{+}1{-}p)\mathcal{E}-p\mathcal{E}_{\pi}-(1{-}p)\mathcal{E}_{\pi^{\prime}}\right\Vert _{\diamond}\nonumber\\
\overset{(2)}{\leq}\left\Vert p\mathcal{E}-p\mathcal{E}_{\pi}\right\Vert
_{\diamond}+\left\Vert (1{-}p)\mathcal{E}-(1{-}p)\mathcal{E}_{\pi^{\prime}}\right\Vert _{\diamond}\nonumber\\
\overset{(3)}{\leq}p\left\Vert \mathcal{E}-\mathcal{E}_{\pi}\right\Vert
_{\diamond}+(1-p)\left\Vert \mathcal{E}-\mathcal{E}_{\pi^{\prime}}\right\Vert
_{\diamond}\nonumber\\
:=pC_{\diamond}(\pi)+(1-p)C_{\diamond}(\pi^{\prime}),\end{gathered}$$ where we use: (1) linearity, (2) triangle inequality, and (3) $\Vert
xA\Vert_{1}=|x|\Vert A\Vert_{1}$ for any operator $A$ and scalar $x$.

In order to apply Theorem \[t:convexC1CF\] and convexily optimize the diamond distance cost, we first fix a program state $\pi$ and compute $C_{\diamond}(\pi)$ by SDP. More precisely, for the computation of the diamond distance, consider the linear map $\Omega_{\pi}:=\mathcal{E}-\mathcal{E}_{\pi}$ with Choi matrix $\chi_{\Omega_{\pi}}=\chi_{\mathcal{E}}-\chi_{\pi}=\chi_{\mathcal{E}}-\Lambda({\pi})$, and the spectral norm $\left\Vert O\right\Vert
_{\infty }:=\max\{\left\Vert Ou\right\Vert
:u\in\mathbb{C}^{d},\left\Vert u\right\Vert \leq1\}$, which is the maximum eigenvalue of $\sqrt{O^{\dagger}O}$. Then, by the strong duality of the diamond norm, $C_{\diamond}(\pi)=\left\Vert \Omega_{\pi}\right\Vert _{\diamond}$ is given by the SDP [@Watrous] $$\begin{gathered}
\text{Minimize }\frac{1}{2}||\mathrm{Tr}_{2}M_{0}||_{\infty}+\frac{1}{2}||\mathrm{Tr}_{2}M_{1}||_{\infty},\nonumber\\
\text{Subject to }\left(
\begin{array}
[c]{cc}M_{0} & -d~\chi_{\Omega_{\pi}}\\
-d~\chi_{\Omega_{\pi}}^{\dagger} & M_{1}\end{array}
\right)  \geq0, \label{SDP}$$ where $M_{0}$ and $M_{1}$ are positive matrices in $\mathbb{C}^{d\times
d^{\prime}}$ [@Karol]. The importance of the above dual formulation is that the diamond distance is a *minimization*, rather than a maximization over a set of matrices. In order to find the optimal program $\tilde{\pi}$ we apply the unique minimization of Eq.  where $\pi$ is variable and satisfies the additional constraints $\pi\geq0$ and $\mathrm{Tr}(\pi)=1$.

A simpler approach which is helpful in deeper designs is the optimization of the larger cost function $C=C_{1}$ or $C_{F}$. Because this is a convex functional $C:\mathcal{S}\mapsto\mathbb{R}$ over the convex set of program states $\mathcal{S}$, we can solve the optimization $\min_{\pi\in\mathcal{S}}C(\pi)$ by using ML gradient-based algorithms. For this purpose, we need to compute the subgradient of $C$ at any point $\pi\in\mathcal{S}$, which is the set$$\partial C(\pi)=\{Z:C(\sigma)-C(\pi)\geq\text{\textrm{Tr}}[Z(\sigma
-\pi)],~\forall\sigma\in\mathcal{S}\},$$ where $Z$ is Hermitian [@nesterov2013introductory; @coutts2018certifying]. If convex $C$ is differentiable, then $\partial C(\pi)$ contains a single element: its gradient $\nabla C(\pi)$. We explicitly compute this gradient for an arbitrary programmable quantum processor, whose map has Kraus decomposition $\Lambda(\pi)=\sum_{k}A_{k}\pi A_{k}^{\dagger}$ with generic operators $A_{k}$. In fact, let us call $\Lambda^{\ast}(\rho)=\sum_{k}A_{k}^{\dagger}\rho A_{k}$ the dual map, then we prove the following [@PRAlong].

\[Theo2\]Consider an arbitrary quantum channel $\mathcal{E}$ with Choi matrix $\chi_{\mathcal{E}}$ which is simulated by a quantum processor $Q$ with map $\Lambda(\pi)=\chi_{\pi}$ (and dual map $\Lambda^{\ast}$). Then, we may write the following gradients for the trace distance cost $C_{1}(\pi)$ and the infidelity cost $C_{F}(\pi)$$$\begin{aligned}
\nabla C_{1}(\pi) &  =\sum_{k}\mathrm{sign}(\lambda_{k})\Lambda^{\ast}(P_{k}),\\
\nabla C_{F}(\pi) &  =-2\sqrt{1-C_{F}(\pi)}\nabla F(\pi),\\
\nabla F(\pi) &  =\frac{1}{2}\Lambda^{\ast}\left[  \sqrt{\chi_{\mathcal{E}}}\left(  \sqrt{\chi_{\mathcal{E}}}\,\Lambda(\pi)\,\sqrt{\chi_{\mathcal{E}}}\right)  ^{-\frac{1}{2}}\sqrt{\chi_{\mathcal{E}}}\right]  ,\label{fidGRAD}$$ where $\lambda_{k}$ ($P_{k}$) are the eigenvalues (eigenprojectors) of the Hermitian operator $\chi_{\pi}-\chi_{\mathcal{E}}$. When $C_{1}(\pi)$ or $C_{F}(\pi)$ are not differentiable in $\pi$, then the above expressions provide an element of the subgradient $\partial C(\pi)$.

Once we have the (sub)gradient of the cost function $C$, we can solve the optimization $\min_{\pi\in\mathcal{S}}C(\pi)$ using the projected subgradient method [@nesterov2013introductory; @boyd2003subgradient]. Let $\mathcal{P}_{\mathcal{S}}$ be the projection onto the set of program states $\mathcal{S}$, namely $\mathcal{P}_{\mathcal{S}}(X)=\mathrm{argmin}_{\pi\in
S}\Vert X-\pi\Vert_{2}$, that we show to be computable from the spectral decomposition of any Hermitian $X$ [@PRAlong]. Then, we iteratively apply the steps $$\begin{array}
[c]{l}1)~\mathrm{Select~an~operator~}g_{i}{~\mathrm{from~}}\partial C(\pi_{i}),\\
2)~\pi_{i+1}=\mathcal{P}_{\mathcal{S}}\left(  \pi_{i}-\alpha_{i}g_{i}\right)
,
\end{array}
\label{projsubgrad}$$ where $i$ is the iteration index and $\alpha_{i}$ is a learning rate. Theorem \[Theo2\] can be employed to find $g_{i}$ at each step and the rate of covergence to the optimal program state $\tilde{\pi}$ is $\mathcal{O}(\epsilon^{-2})$ steps where $|C(\pi)-C(\tilde{\pi})|\leq\epsilon$. Another approach is the conjugate gradient method [@jaggi2011convex; @nesterov2013introductory], sometimes called Frank-Wolfe algorithm. Here, we apply $$\begin{array}
[c]{l}1)~\text{\textrm{Find the smallest eigenvalue}}~\left\vert \sigma
_{i}\right\rangle ~\text{\textrm{of}}~\nabla C(\pi_{i}),\\
2)~\pi_{i+1}=\frac{i}{i+2}\pi_{i}+\frac{2}{i+2}\left\vert \sigma
_{i}\right\rangle \left\langle \sigma_{i}\right\vert .
\end{array}
\label{FrankWolfe}$$ When the gradient of $f$ is Lipschitz continuous with constant $L$, the method converges after $\mathcal{O}(L/\epsilon)$ steps [@jaggi2013revisiting; @nesterov2005smooth]. To justify the applicability of this method a suitable smoothening of the cost function must be employed [^1].

*Learning of arbitrary unitaries*.– One specific application is the simulation of quantum gates or, more generally, unitary transformations [@lloyd1996universal; @khaneja2005optimal; @banchi2016quantum; @innocenti2018supervised; @mitarai2018quantum; @arrazola2018machine]. Here, if we use the infidelity cost function, the solution is analytical. In fact, suppose we use a quantum processor with map $\Lambda$ to simulate a target unitary $U$. Because the Choi matrix of $U$ is pure $|\chi_{U}\rangle
\langle\chi_{U}|$, we first note that $F(\pi)=\langle\chi_{U}|\Lambda
(\pi)|\chi_{U}\rangle$ and then we see that Eq. (\[fidGRAD\]) drastically simplifies to $\nabla F(\pi)=\Lambda^{\ast}\left(  |\chi_{U}\rangle\langle
\chi_{U}|\right)  /\sqrt{4F(\pi)^2}$. As a result, we find $$\nabla C_{F}(\pi)=-\Lambda^{\ast}\left[  |\chi_{U}\rangle\langle\chi
_{U}|\right]  ,$$ where there is no dependence on $\pi$. Therefore, using the conjugate gradient method in Eq. , we see that the optimal program state $\tilde{\pi}$ for the infidelity cost function $C_{F}$ is a fixed point of the iteration and is equal to the maximum eigenvector of $\Lambda^{\ast
}\left[  |\chi_{U}\rangle\langle\chi_{U}|\right]  $.

*Shallow and deep designs*.– Once we have shown how to optimize a generic programmable quantum processor, we discuss some specific designs, over which we will test the optimization procedure. One possible (shallow) design for the quantum processor $Q$ is a generalized teleportation protocol [@bennett1993teleporting] over an arbitrary program state $\pi$. In dimension $d$, the protocol involves a basis of $d^{2}$ maximally-entangled states $|\Phi_{i}\rangle$ and a basis $\{U_{i}\}$ of teleportation unitary such that $\mathrm{Tr}(U_{i}^{\dagger}U_{j})=d\delta_{ij}$ [@teleREVIEW]. An input $d$-dimensional state $\rho$ and the $A$ part of the program $\pi_{AB}$ are subject to the projector $|\Phi_{i}\rangle\left\langle \Phi
_{i}\right\vert $. The classical outcome $i$ is communicated to the $B$ part of $\pi_{AB}$ where the correction $U_{i}^{-1}$ is applied.

In this way, we define a teleportation channel $\mathcal{E}_{\pi}$ over $\rho
$. Its Choi matrix can be written as $\chi_{\pi}=\Lambda_{\text{tele}}(\pi)$, where the map of the teleportation processor is equal to$$\Lambda_{\text{tele}}(\pi)=d^{-2}\sum_{i}\left(  U_{i}^{\ast}\otimes
U_{i}\right)  \pi\left(  U_{i}^{\ast}\otimes U_{i}\right)  ^{\dagger},
\label{eqAB}$$ which is clearly self-dual $\Lambda^{\ast}=\Lambda$. Given a target quantum channel $\mathcal{E}$ which is teleportation-covariant [@pirandola2017fundamental; @commREVIEW], we know that its simulation is perfect and the optimal program $\tilde{\pi}$ is the channel’s Choi matrix, i.e., one of the fixed points of the map $\Lambda
_{\text{tele}}$. For a general channel, the optimal program $\tilde{\pi}$ can be approximated by using the cost functions in our Theorem \[Theo2\] with $\Lambda$ being given in Eq. (\[eqAB\]), or directly found by optimizing $C_{\diamond}(\pi) $.

A deeper design is provided by a PBT processor. Here we consider a more general formulation of the original PBT protocol [@ishizaka2008asymptotic; @ishizaka2009quantum] where the resource entangled pairs are replaced by an arbitrary program state $\pi$. In a PBT processor, each party has $N$ systems (or ‘ports’), $\mathbf{A}=\{A_{1},\dots,A_{N}\}$ for Alice and $\mathbf{B}=\{B_{1},\dots,B_{N}\}$ for Bob. These are prepared in a program state $\pi_{\mathbf{AB}}$. To teleport an input state $\rho_{C}$, Alice performs a joint POVM $\{\Pi_{i}\}$ [@ishizaka2008asymptotic] on system $C$ and the $\mathbf{A}$-ports. She then communicates the outcome $i$ to Bob, who discards all ports except $B_{i}$ which is the output $B_{\text{out}}$. Consider an input maximally-entangled state $|\Phi_{DC}\rangle$ and a basis $|e_{j}^{i}\rangle$ of $\mathbf{A}\{\mathbf{B}\backslash B_{i}\}C$, then the map $\Lambda
_{\mathbf{AB}\rightarrow DB_{\text{out}}}$ of a PBT processor takes the form$$\Lambda(\pi)={\textstyle\sum_{ij}}
K_{ij}\pi K_{ij}^{\dagger},~K_{ij}:=\langle{e_{j}^{i}}|\sqrt{\Pi_{i}}\otimes\openone_{BD}|\Phi_{DC}\rangle. \label{PBTmap2}$$ Given a target channel $\mathcal{E}$, the optimal program $\tilde{\pi}$ can be approximated by using the cost functions in our Theorem \[Theo2\] with $\Lambda$ being given in Eq. (\[PBTmap2\]), or it may be directly found by optimizing $C_{\diamond}(\pi)$.

Note that a general program state for PBT consists of $2N$ qudits, and hence the parameter space has exponential size $d^{4N}$. However, because the PBT protocol is symmetric under permutation of port labels, we can exploit this symmetry and reduce the number of free parameters to the binomial coeffficient $\binom{N+d^{4}-1}{d^{4}-1}$, which is polynomial in the number of ports $N$ [@PRAlong]. Despite this exponential reduction, the scaling in the number of parameters still represents a practical limiting factor, even for qubits for which $\mathcal{O}\left(  N^{15}\right)  $. A sub-optimal strategy consists in reducing the space of program states to a convex set that we call the Choi space $\mathcal{C} $. Consider an arbitrary probability distribution $\{p_{k}\}$ and then define $$\mathcal{C}=\{\pi:\pi={\textstyle\sum_{k}}
p_{k}\rho_{AB}^{k\otimes N},~\mathrm{Tr}_{B}(\rho_{AB}^{k})=d^{-1}\openone\}.
\label{Choispace}$$

One can show [@PRAlong] that a global minimum in $\mathcal{C}$ is a global minimum in the extremal (non-convex) subspace for $p_{k}=\delta_{k,1}$ consisting of tensor-products of Choi matrices $\rho_{AB}^{\otimes N}$. Among these states, there is the $N$-copy Choi matrix of the target channel $\chi_{\mathcal{E}}^{\otimes N}=[\mathcal{I}\otimes\mathcal{E}(|\Phi
\rangle\left\langle \Phi\right\vert )]^{\otimes N}$ which is not necessarily the optimal program, as we show below. Note that, if the channel’s Choi matrix is used as program state, then the PBT-simulated channel can be decomposed as $\mathcal{E}_{\pi}=\mathcal{E}\circ\mathcal{I}_{N}$, where $\mathcal{I}_{N}$ is the PBT approximation of the identity channel, satisfying [@pirandola2018fundamental] $$\delta_{N}^{d}:=||\mathcal{I}-\mathcal{I}_{N}||_{\diamond}\leq2d(d-1)N^{-1}~.$$ Using data processing, this leads to the bound $C_{\diamond}\leq\delta_{N}^{d}$, for the simulation of any channel. While the channel’s Choi matrix assures that $\delta_{N}^{d} \rightarrow 0$ for large $N$, for any finite $N$ it does not represent the optimal program state.

Another deep design of quantum processor is based on PQCs [@lloyd1995almost; @lloyd1996universal]. A PQC is a sequence of unitary matrices $U(t)=U_{N}(t_{N})\dots U_{2}(t_{2})U_{1}(t_{1})$, where $U_{j}(t_{j})=\exp(it_{j}H_{j})$ for some Hamiltonian $H_{j}$ and time interval $t_{j}$. Sequences of two unitaries, $U_{0}$ and $U_{1}$, are almost universal [@lloyd1995almost], i.e., any target unitary $U$ can be approximated as $U\approx\cdots U_{1}^{m_{4}}U_{0}^{m_{3}}U_{1}^{m_{2}}U_{0}^{m_{1}}$ for some integers $m_{j}$. Under suitable conditions, it takes $\mathcal{O}(d^{2}\epsilon^{-d})$ steps to approximate $U$ up to precision $\epsilon$. The problem with PQCs is that the cost functions in the classical parameters [@khaneja2005optimal] are not convex, so that numerical algorithms are not guaranteed to converge to the global optimum. Here we fix this issue by introducing a convex formulation of PQCs where classical parameters are replaced by a quantum program. This results into a programmable PQC processor which is optimizable by our methods.

Consider a pure program state $|\pi\rangle=|\theta_{0}\rangle\otimes
\cdots\otimes|1\rangle^{\otimes m_{2}}\otimes|0\rangle^{\otimes m_{1}}$ defined over a register of qubits $R=(R_{0},\dots,R_{N})$ and embedding the parameters $m$’s (note that, more generally, our formulation allows us to consider entangled program states). Then, consider the conditional unitaries $$\tilde{U}_{j}=e^{it_{0}H_{0}^{AR_{0}}\otimes|0\rangle_{R_{j}}\langle
0|+it_{1}H_{1}^{AR_{0}}\otimes|1\rangle_{R_{j}}\langle1|}, \label{condAB}$$ which act on an input qubit $A$ and two register qubits $R_{0}$ and $R_{j}$. For any input state $\rho_{A}$, our PQC processor realizes the quantum channel$$\mathcal{E}_{\pi}(\rho_{A})=\mathrm{Tr}_{R}\left[  \prod_{j=1}^{N}\tilde
{U}_{j}\left(  \rho_{A}\otimes\pi_{R}\right)  \prod_{j=1}^{N}\tilde{U}_{j}^{\dagger}\right]  . \label{EPQC}$$ There must exist a separable state $|\tilde{\pi}\rangle$ for which we can write $\mathcal{E}_{\tilde{\pi}}(\rho)\approx\mathrm{Tr}_{R_{0}}[U(\rho
\otimes\theta_{0})U^{\dagger}]$ where $U$ is the target unitary. This means that $\mathcal{E}_{\tilde{\pi}}$ is able to approximate an arbitrary target channel $\mathcal{E}$ via the Stinespring dilation. By partly propagating a maximally-entangled state through $\mathcal{E}_{\pi}$ in Eq. (\[EPQC\]) we find the processor map $\Lambda(\pi)$ from which we can identify the optimal program $|\tilde{\pi}\rangle$ via our methods.

![Diamond-distance error $C_{\diamond}$ in simulating an amplitude damping channel $\mathcal{E}_{p}$ at various damping rates $p$. We compare the performance of different designs for the programmable quantum processor: Standard teleportation, port-based teleportation with $N$ ports (PBT$_{N}$), and a processor based on parametric quantum circuits with $N+1$ registers (PQC$_{N}$). In (a) the optimal program $\tilde{\pi}$ is obtained by either minimizing directly the diamond distance $C_{\diamond}$ (solid lines), or the trace distance $C_{1}$ (dashed lines) via the projected subgradient iteration. In both cases, from $\tilde{\pi}$ we then compute $C_{\diamond
}(\tilde{\pi})$. The lowest curves are obtained by optimizing $\pi$ over the Choi space in Eq. (\[Choispace\]). For comparison, we also show the (non-optimal) performance when the program is the channel’s Choi matrix (dotted lines). In (b) the optimal program $|\tilde{\pi}\rangle$ is obtained by minimizing the diamond distance $C_{\diamond}$. []{data-label="fig:ad"}](ad2.pdf){width="1.0\linewidth"}

*Processor benchmarking*.– In order to show the performance of the various architectures, we consider the simulation of an amplitude damping channel with probability $p$. The reason is because this is the most difficult channel to simulate, with a perfect simulation only known for infinite dimension, e.g., using with continuous-variable quantum operations [@pirandola2017fundamental]. In Fig. \[fig:ad\] we compare teleportation-based, PBT and PQC programmable processors whose program states have been optimized according to the cost functions $C_{\diamond}$ and $C_{1}$. For the PBT processor the trace distance cost $C_{1}$ is remarkably close to $C_{\diamond}$ and allows us to easily explore high depths. Note that the optimal program states differ from naive choice of Choi matrix of the target channel. Also note that the superior performance of shallow PQC processors in simulating the amplitude damping channel (e.g., for $N=4$), even though there is some fluctuation [^2]. This non-monotonic behaviour may appear in PQCs at any $N$.

*Conclusions*.– In this work we have shown that the optimization of a general finite-dimensional model of programmable quantum processor is a convex problem in the set of program states, so that an optimal program can always be found by means of SDP or gradient-based ML techniques. This is possible by using various relevant cost functions, from the exact diamond distance to larger but more computable functionals, such as the trace distance and the quantum fidelity.

We have then applied our results to various types of quantum processor, from a shallow-depth scheme based on standard teleportation to deeper schemes relying on port-based teleportation and parametric quantum circuits (suitably reformulated). We have explicitly benchmarked their performances with respect to the simulation of amplitude damping channels, with further details and results presented in our companion paper [@PRAlong].

The optimal learning of quantum programs has direct implications in many areas of quantum information, not only for quantum computing (and blind quantum computing) but also for investigating the ultimate limits of quantum communications [@commREVIEW], designing optimal Hamiltonians for one-way quantum repeaters, and all those areas of quantum sensing, hypothesis testing and metrology which are based on quantum channel simulations [@sensingREVIEW].

**Acknowledgements. ** L.B. acknowledges support by the program “Rita Levi Montalcini” for your young researchers. S.P. acknowledges support by the EPSRC via the ‘UK Quantum Communications Hub’ (EP/M013472/1) and the European Union via the project ‘Continuous Variable Quantum Communications’ (CiViQ, no 820466). S.P. would like to thank George Zweig, Jacques Carolan, John Watrous, and Dirk Englund for discussions and feedback.

[^1]: The downside of the conjugate gradient method is that it necessarily requires a differentiable cost function $C$, with gradient $\nabla
    C$. Specifically, this may create problems for the trace distance cost $C_{1}$ which is generally non-smoth. A solution to this problem is to define the cost function in terms of the smooth trace distance $C_{\mu}(\pi)=\mathrm{Tr}\left[  h_{\mu}\left(  \chi_{\pi}-\chi_{\mathcal{E}}\right)
    \right]  $ where $h_{\mu}$ is the so-called Huber penalty function $h_{\mu}(x):=x^{2}/(2\mu) \mathrm{~if~}|x|<\mu$ and $|x|-\mu/2
    \mathrm{~if~}|x|\geq\mu.$ This quantity satisfies $C_{\mu}(\pi)\leq C_{1}(\pi)\leq
    C_{\mu}(\pi)+\mu d/2 $ and is a convex function over program states, with gradient $\nabla
    C_{\mu}(\pi)=\Lambda^{\ast}[h_{\mu}^{\prime}(\chi_{\pi}-\chi
    _{\mathcal{E}})] $.

[^2]: For the PQC processor we use the universal Hamiltonians $H_{0}=\sqrt{2}(X\otimes Y-Y\otimes X)$ and $H_{1}=(\sqrt{2}Z{+}\sqrt{3}Y{+}\sqrt{5}X)\otimes(Y{+}\sqrt{2}Z)$, where $X$, $Y$, and $Z$ are Pauli operators.
