Noise-tolerant parity learning with one quantum bit

Demonstrating quantum advantage with less powerful but more realistic devices is of great importance in modern quantum information science. Recently, a significant quantum speedup was achieved in the problem of learning a hidden parity function with noise. However, if all data qubits at the query output are completely depolarized, the algorithm fails. In this work, we present a quantum parity learning algorithm that exhibits quantum advantage as long as one qubit is provided with nonzero polarization in each query. In this scenario, the quantum parity learning naturally becomes deterministic quantum computation with one qubit. Then the hidden parity function can be revealed by performing a set of operations that can be interpreted as measuring nonlocal observables on the auxiliary result qubit having nonzero polarization and each data qubit. We also discuss the source of the quantum advantage in our algorithm from the resource-theoretic point of view.

Figure 1

The quantum circuit for the parity learning algorithm in Ref. [11]. Hadamard operations $\left(H\right)$ prepare the equal superposition of all possible input states. The hidden parity function (gray box) is realized using controlled-not gates between the result (target) and data (control) qubits. The hidden bit string $s=011...0$ is used as an example. All qubits are measured in their computational bases at the end.

Figure 2

The DQC1 circuit that implements the original quantum parity learning algorithm with fully depolarized data qubits. The gray box represents the hidden function defined by $s=011...0$ as an example. The data qubits at the query input are in the completely mixed state, but the result qubit is prepared with nonzero polarization $\alpha$. The expectation measurement replaces the projective measurement, and it returns the normalized trace of the unitary matrix that corresponds to the hidden parity function. The result qubit also experiences depolarizing noise $\left({\mathcal{D}}_p\right)$ prior to the measurement as in the original algorithm. The trace is zero for all $s$ except when it is uniformly 0.

Figure 3

The modified DQC1 circuit for solving the LPN problem. The gray box represents the hidden function defined by $s=011...0$ as an example. The quantum learner applies the uniform rotation to all data qubits controlled by the result qubit except on the $j\mathrm{th}$ qubit $\left[R_x^{\overline{j}}\left(\theta \right)\right]$. For some $\theta$, the trace of the total unitary operator is 0 (nonzero) if the hidden bit encoded in the $j\mathrm{th}$ data qubit is 1 (0).

Figure 4

A phase-flip $\left(Z\right)$ on the second qubit after a gate sequence constructed as a Hadamard followed by a cnot is equivalent to a bit-flip $\left(X\right)$ on the first qubit and a phase-flip on the second qubit before the gate sequence.

Figure 5

Quantum discord at the end of the DQC1 circuit shown in Fig. 3 as a function of $\alpha$ for various $s$. In this regime, there is no entanglement in the result-data bipartition. The amount of discord depends on the hidden bit value encoded in the $j\mathrm{th}$ data qubit, which is excluded from the uniform rotation prior to the measurement [see Eq. (9)]. For all $s$, the discord is the same when $s_j=1$ (solid line). The inset shows the difference of the discord for $s_j=1$ and $s_j=0$ as a function of the controlled-rotation angle $\theta$ when $s=10$ and $\alpha =1/4$.