Practical quantum appointment scheduling

We propose a protocol based on coherent states and linear optics operations for solving the appointment-scheduling problem. Our main protocol leaks strictly less information about each party's input than the optimal classical protocol, even when considering experimental errors. Along with the ability to generate constant-amplitude coherent states over two modes, this protocol requires the ability to transfer these modes back-and-forth between the two parties multiple times with very low losses. The implementation requirements are thus still challenging. Along the way, we develop tools to study quantum information cost of interactive protocols in the finite regime.

Figure 1

Depiction of main quantum subroutine ${\tilde{\mathrm{\Pi }}}_A$. Coherent state $|\alpha \rangle |0\rangle$ is prepared at the outset. For $r$ rounds, Alice either returns the coherent states directly or apply a beam splitter with splitting ratio 1/$r$. Bob either discard the coherent states and reinjects new ones, or returns the coherent states directly. After $r$ rounds, the two modes are each sent to a single photon threshold detector.

Figure 2

The $O\left(n^{2/3}\right)$ limiting behavior of our quantum protocol in comparison with the $\mathrm{\Omega }\left(n\right)$ classical lower bound in the ideal setting for zero error. We have chosen the number of rounds $r=n^{1/3}$, the coherent-state amplitude $\alpha =1$, and subsample size $s=n^{2/3}$. The information leakage ($\mathrm{QIC}$) measured in bits divided by the input size $n$ is plotted on the $y$ axis and the input size $n$ on the $x$ axis. The simple choice of parameters used in this plot demonstrates the $O\left(n^{2/3}\right)$ limiting behavior but is suboptimal for smaller values of $n$. See Fig. 4 for an optimized plot of the QIC at lower values of $n$.

Figure 3

Depiction of $r$ on the left and $\alpha$ on the right, optimized to minimize the information leakage, as functions of the transmissivity $\eta$ for fixed $n={10}^{15}, p_{\mathrm{dark}}=4\times {10}^{-8}$, and ${\eta }_{\det }=0.9$, under the choice $s=0.001n$. At $\eta =1$ the optimal values are $\alpha =1.47$ and $r=1798$.

Figure 4

Depiction of the quantum advantage in terms of information leakage ($\mathrm{QIC}$) measured in bits and comparison of the classical lower bounds for both zero-error and $\varepsilon$-error protocols to the quantum upper bound both for an ideal experimental setup and for setups accounting for experimental errors with the following parameters: transmissivity $\eta =0.99$, dark count probability $p_{\mathrm{dark}}=\varepsilon =4\times {10}^{-8}$, and detection efficiency ${\eta }_{\det }=0.9$. At each point we have optimized over $s, \alpha$, and $r$. The value of $s$ obtained by our optimization decreases from around $s=0.1n$ to $s=0.001n$ as $n$ increases from ${10}^7$ to ${10}^{11}$. The optimized value of $r$ increases with $n$ from around $r=30$ to around $r=100$ and the optimized value of $\alpha$ remains near $\alpha =1$. The information leakage divided by the input size $n$ is plotted on the $y$ axis and the input size $n$ on the $x$ axis. Note that the classical information leakage lower bound with nonzero error could probably be made much closer to the one at zero error by a careful analysis of Refs. [19, 20] in the finite regime.

Figure 5

Depiction of the quantum advantage in terms of information leakage ($\mathrm{QIC}$) measured in bits as a function of the loss parameter $\eta$. Plotted on the left is a similar comparison to the classical protocols as in Fig. 4, but for different values of ${\eta }_{\det }$, and on the right the classical over quantum ratio for $n={10}^{15}$ and $n={10}^{30}$. We have used $s=0.001n$, which we have found performs very well for this range of $\eta$. We can see that for $p_{\mathrm{dark}}=4\times {10}^{-8}$ and ${\eta }_{\det }=0.9$, we begin to get a quantum advantage for $\eta \approx 0.975$, and the advantage grows as $\eta$ goes to one. In particular, for $\eta =0.999$, we get an improvement by a factor of more than 14. Note that we have implicitly optimized $r$ and $\alpha$ as functions of $\eta$ here to obtain the greatest advantage.

Figure 6

Depiction of an interactive quantum protocol, adapted from the long version of Fig. 1 in [17]. More details about the model of quantum communication can be found there.