Random unsolved problem

Unsolved op_3b3bfcda365a83a9

Linear-size exact quantum Fourier transform

Can the exact quantum Fourier transform on \(n\) qubits be implemented with \(O(n)\) one- and two-qubit gates?

Define

\begin{equation} F_{2^n}|x\rangle=2^{-n/2}\sum_{y=0}^{2^n-1}e^{2\pi ixy/2^n}|y\rangle. \tag{1} \end{equation}

Let \(C_{\mathrm{exact}}(n)\) be the minimum size of a uniform circuit that implements the unitary in Eq. (1) exactly on arbitrary inputs. Gates may be arbitrary efficiently specified one- or two-qubit unitaries; clean ancillas may be used but must be restored, and all gates on them count. Is

\begin{equation} C_{\mathrm{exact}}(n)=O(n)? \tag{2} \end{equation}

The target in Eq. (2) concerns exact coherent implementation, not approximate QFT or sampling only.

Open problem page

Random solved problem

Solved op_89fb664ba06ba5de

Candidate pure-loss second-order converse

Does the pure-loss bosonic channel admit the following candidate second-order classical converse under a maximum-photon-number occupation constraint? Let \(\mathcal N_\eta\) be the single-mode pure-loss channel with transmissivity \(0<\eta<1\), defined in the Heisenberg picture by

\begin{equation} \hat b=\sqrt{\eta}\,\hat a+\sqrt{1-\eta}\,\hat e, \tag{1} \end{equation}

where the environment mode \(E\) is in the vacuum. In an \(n\)-use code, the channel in Eq. (1) is used to transmit one of \(M\) input states \(\rho_m^{A^n}\), with a decoding POVM \(\{\Lambda_m^{B^n}\}_{m=1}^M\). Write \(\overline\rho_{A^n}:=M^{-1}\sum_m\rho_m^{A^n}\) and let \(\Pi_{\lceil nN_S\rceil}\) project onto the \(n\)-mode subspace of total photon number at most \(\lceil nN_S\rceil\). For fixed \(N_S>0\), \(\varepsilon\in(0,1)\), and \(c>0\), impose

\begin{equation} \frac1M\sum_{m=1}^M \operatorname{Tr}\!\left[ \Lambda_m\mathcal N_\eta^{\otimes n}(\rho_m) \right] \geq1-\varepsilon, \qquad \operatorname{Tr}\!\left[ \Pi_{\lceil nN_S\rceil}\overline\rho_{A^n} \right] \geq1-\delta_n, \qquad 0\leq\delta_n\leq2^{-cn}. \tag{2} \end{equation}

Let \(M^*_{\rm occ}(n,\eta,N_S,\varepsilon,c)\) be the largest \(M\) satisfying Eq. (2). Define the thermal entropy and its entropy variance by

\begin{equation} g(x):=(x+1)\log_2(x+1)-x\log_2x, \qquad v(x):=x(x+1) \left[\log_2(x+1)-\log_2x\right]^2, \tag{3} \end{equation}

where \(0\log_2 0:=0\). With the functions in Eq. (3), is the following upper bound valid as \(n\to\infty\)?

\begin{equation} \log_2 M^*_{\rm occ}(n,\eta,N_S,\varepsilon,c) \leq ng(\eta N_S) +\sqrt{n\,v(\eta N_S)}\,\Phi^{-1}(\varepsilon) +O(\log n), \tag{4} \end{equation}

Here \(\Phi^{-1}\) in Eq. (4) is the inverse standard-normal cumulative distribution function, and the implicit constant may depend on \(\eta,N_S,\varepsilon,\) and \(c\), but not on \(n\).

Open problem page

Activity

Recently edited

All problems by date →