Polarization requirements for ensemble implementations of quantum algorithms with a single-bit output

We compare the failure probabilities of ensemble implementations of quantum algorithms which use pseudopure initial states, quantified by their polarization, to those of competing classical probabilistic algorithms. Specifically we consider a class algorithms which require only one bit to output the solution to problems. For large ensemble sizes, we present a general scheme to determine a critical polarization beneath which the quantum algorithm fails with greater probability than its classical competitor. We apply this to the Deutsch-Jozsa algorithm and show that the critical polarization is 86.6%.

Figure 1

Quantum circuit for the standard version of the Deutsch-Jozsa algorithm. The actions of the gates are defined in the text and the algorithm terminates with a computational basis measurement on all $n$ control register qubits.

Figure 2

Modified quantum circuit which produces a single bit output for the Deutsch-Jozsa problem. The final gate is a multiply controlled NOT which applies a NOT to the target register when every argument register qubit is in state $\mid 0⟩$.

Figure 3

Critical polarization vs ensemble size for the Deutsch-Jozsa algorithm. The solid line is generated via Eq. (32) while the dashed line is generated via Eq. (31). The squares display data obtained by solving Eq. (30) numerically for the best resolution case, while the asterisks are for a resolution $R=\sqrt{M}$.