2005/08/07 by Brandon Anderson, Brandon M. Anderson, David C. Collins +1
Computer Science · Physics and Astronomy · #Neural Networks and Reservoir Computing #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #quant-ph
paper · pdf · doi:10.1103/physreva.72.042337
11 pages, 3 figures
arxiv created 2005/08/07 · openalex publication_date 2005/10/28 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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%.