Space-Efficient Quantum Error Reduction without log Factors
Summarize this article with:
AbstractGiven an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth. Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.Featured image: Quantum walk on an infinite line.Popular summaryAn interesting phenomenon in quantum algorithms is that even bounded-error quantum algorithms can be composed without log factors. This is accomplished by turning each bounded-error subroutine into a representation (called a transducer) that is, in some sense perfect, and composing these transducers, and then mapping the result back to a bounded-error quantum algorithm. The process of turning a bounded-error quantum algorithm into a transducer with no perturbation is called purification. In this paper, we give a a more efficient method of purification. It has better space complexity, better dependence on the initial error, and it has a natural and intuitive structure, corresponding to a quantum walk on an infinite line.► BibTeX data@article{Belovs2026spaceefficient, doi = {10.22331/q-2026-03-23-2039}, url = {https://doi.org/10.22331/q-2026-03-23-2039}, title = {Space-{E}fficient {Q}uantum {E}rror {R}eduction without log {F}actors}, author = {Belovs, Aleksandrs and Jeffery, Stacey}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2039}, month = mar, year = {2026} }► References [1] S. Aaronson, R. Kothari, W. Kretschmer, and J. Thaler. Quantum lower bounds for approximate counting via Laurent polynomials. In Proc. of 35th IEEE CCC, volume 169 of LIPIcs, pages 7:1–7:47, 2020. arXiv:1904.08914. https://doi.org/10.4230/LIPIcs.CCC.2020.7 arXiv:1904.08914 [2] A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. Earlier: FOCS'04, arXiv:quant-ph/0311001. https://doi.org/10.1137/S0097539705447311 arXiv:quant-ph/0311001 [3] A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang. Any AND-OR formula of size $N$ can be evaluated in time $N^{1/2+o(1)}$ on a quantum computer. SIAM Journal on Computing, 39(6):2513–2530, 2010. Earlier: FOCS'07. https://doi.org/10.1137/080712167 [4] A. Ambainis, L. Magnin, M. Rötteler, and J. Roland. Symmetry-assisted adversaries for quantum state generation. In Proc. of 26th IEEE CCC, pages 167–177, 2011. arXiv:1012.2112. https://doi.org/10.1109/CCC.2011.24 arXiv:1012.2112 [5] A. Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013. arXiv:1302.3143 [6] A. Belovs. Variations on quantum adversary. arXiv:1504.06943, 2015. arXiv:1504.06943 [7] A. Belovs. Global phase helps in quantum search: Yet another look at the welded tree problem. arXiv:2404.19476, 2024. arXiv:2404.19476 [8] A. Belovs, S. Jeffery, and D. Yolcu. Taming quantum time complexity. Quantum, 8:1444, 2024. arXiv:2311.15873. https://doi.org/10.22331/q-2024-08-23-1444 arXiv:2311.15873 [9] A. Belovs and T. Lee. Quantum algorithm for $k$-distinctness with prior knowledge on the input. arXiv:1108.3022, 2011. arXiv:1108.3022 [10] A. Belovs and A. Rosmanis. Tight quantum lower bound for approximate counting with quantum states. arXiv:2002.06879, 2020. arXiv:2002.06879 [11] A. Belovs and D. Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023. arXiv:2301.02003 [12] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. Earlier: STOC'93. https://doi.org/10.1137/S0097539796300921 [13] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation.
In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53–74, 2002. arXiv:quant-ph/0005055. arXiv:quant-ph/0005055 [14] H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In Proc. of 40th IEEE FOCS, pages 358–368, 1999. arXiv:cs/9904019. https://doi.org/10.1109/SFFCS.1999.814607 arXiv:cs/9904019 [15] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey.
Theoretical Computer Science, 288:21–43, 2002. https://doi.org/10.1016/S0304-3975(01)00144-X [16] A. M. Childs, R. Cleve, S. P. Jordan, and D. Yonge-Mallo. Discrete-query quantum algorithm for nand trees. Theory OF Computing, 5:119–123, 2009. arXiv:quant-ph/0702160. https://doi.org/10.4086/toc.2009.v005a005 arXiv:quant-ph/0702160 [17] A. Cornelissen, S. Jeffery, M. Ozols, and A. Piedrafita. Span programs and quantum time complexity. In Proc. of 45th MFCS, pages 26:1–26:14, 2020. arXiv:2005.01323. https://doi.org/10.4230/LIPIcs.MFCS.2020.26 arXiv:2005.01323 [18] P. G. Doyle and J. L. Snell. Random walks and electric networks, volume 22 of Carus Mathematical Monographs. MAA, 1984. arXiv:math.PR/0001057. arXiv:math.PR/0001057 [19] E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4:169–190, 2008. arXiv:quant-ph/0702144. https://doi.org/10.4086/toc.2008.v004a008 arXiv:quant-ph/0702144 [20] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proc. of 51st ACM STOC, pages 193–204, 2019. arXiv:1806.01838. https://doi.org/10.1145/3313276.3316366 arXiv:1806.01838 [21] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pages 212–219, 1996. arXiv:quant-ph/9605043. https://doi.org/10.1145/237814.237866 arXiv:quant-ph/9605043 [22] P. Høyer, T. Lee, and R. Špalek. Negative weights make adversaries stronger. In Proc. of 39th ACM STOC, pages 526–535, 2007. arXiv:quant-ph/0611054. https://doi.org/10.1145/1250790.1250867 arXiv:quant-ph/0611054 [23] T. Ito and S. Jeffery. Approximate span programs. Algorithmica, 81(6):2158–2195, 2019. arXiv:1507.00432. arXiv:1507.00432 [24] S. Jeffery. Span programs and quantum space complexity. Theory of Computing, 18(11):1–49, 2022. arXiv:1908.04232. https://doi.org/10.4086/toc.2022.v018a011 arXiv:1908.04232 [25] S. Jeffery. SIGACT News Complexity Theory Column 123: Composing quantum algorithms. ACM SIGACT News, 55(4):49–69, December 2024. [26] S. Jeffery and F. Witteveen. $\mathsf{QMA} = \mathsf{QMA}_1$ with an infinite counter. arXiv:2506.15551, 2025. arXiv:2506.15551 [27] S. Jeffery and S. Zur. Multidimensional quantum walks, with application to k-distinctness. In Proc. of 55th ACM STOC, pages 1125–1130, 2023. arXiv:2208.13492. https://doi.org/10.1145/3564246.3585158 arXiv:2208.13492 [28] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proc. of 52nd IEEE FOCS, pages 344–353, 2011. arXiv:1011.3020. https://doi.org/10.1109/FOCS.2011.75 arXiv:1011.3020 [29] G. H. Low and I. L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv:1707.05391, 2017. arXiv:1707.05391 [30] G. H. Low, T. J. Yoder, and I. L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6(4):041067, 2016. arXiv:1603.03996. https://doi.org/10.1103/PhysRevX.6.041067 arXiv:1603.03996 [31] C. Marriott and J. Watrous. Quantum Arthur–Merlin games. Computational Complexity, 14(2):122–152, 2005. Earlier: CCC'04, arXiv:cs/0506068. https://doi.org/10.1007/s00037-005-0194-x arXiv:cs/0506068 [32] D. Nagaj, P. Wocjan, and Y. Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11-12):1053–1068, 2009. arXiv:0904.1549. https://doi.org/10.5555/2012098.2012106 arXiv:0904.1549 [33] A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proc. of 31st ACM STOC, pages 384–393, 1999. arXiv:quant-ph/9804066. https://doi.org/10.1145/301250.301349 arXiv:quant-ph/9804066 [34] G. Pólya. Über eine aufgabe der wahrscheinlichkeitsrechnung betreffend die irrfahrt im straßennetz. Mathematische Annalen, 84(1):149–160, 1921. [35] P. Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5:566, 2021. arXiv:2103.09717. https://doi.org/10.22331/q-2021-10-19-566 arXiv:2103.09717 [36] B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. of 50th IEEE FOCS, pages 544–551, 2009. arXiv:0904.2759. https://doi.org/10.1109/FOCS.2009.55 arXiv:0904.2759 [37] B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8:291–319, 2012. Earlier: STOC'08, arXiv:0710.2630. https://doi.org/10.4086/toc.2012.v008a013 arXiv:0710.2630Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-23 12:23:47: Could not fetch cited-by data for 10.22331/q-2026-03-23-2039 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-23 12:23:48: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractGiven an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ – e.g., if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. Transducers are a recently introduced model of quantum computation, and it is possible to reduce the “error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called purification. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. Our purifier has much smaller space and time complexity than the previous one. Indeed, it only uses one additional counter, and only performs two increment and two decrement operations on each iteration. It also has quadratically better dependence on the soundness-completeness gap of the algorithm being purified. We prove that our purifier has optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth. Purifiers can be seen as a way of turning a “Monte Carlo'' quantum algorithm into a “Las Vegas'' quantum algorithm – a process for which there is no classical analogue. Our simplified construction sheds light on this strange quantum phenomenon, and could have implications for the complexity of composed quantum algorithms.Featured image: Quantum walk on an infinite line.Popular summaryAn interesting phenomenon in quantum algorithms is that even bounded-error quantum algorithms can be composed without log factors. This is accomplished by turning each bounded-error subroutine into a representation (called a transducer) that is, in some sense perfect, and composing these transducers, and then mapping the result back to a bounded-error quantum algorithm. The process of turning a bounded-error quantum algorithm into a transducer with no perturbation is called purification. In this paper, we give a a more efficient method of purification. It has better space complexity, better dependence on the initial error, and it has a natural and intuitive structure, corresponding to a quantum walk on an infinite line.► BibTeX data@article{Belovs2026spaceefficient, doi = {10.22331/q-2026-03-23-2039}, url = {https://doi.org/10.22331/q-2026-03-23-2039}, title = {Space-{E}fficient {Q}uantum {E}rror {R}eduction without log {F}actors}, author = {Belovs, Aleksandrs and Jeffery, Stacey}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2039}, month = mar, year = {2026} }► References [1] S. Aaronson, R. Kothari, W. Kretschmer, and J. Thaler. Quantum lower bounds for approximate counting via Laurent polynomials. In Proc. of 35th IEEE CCC, volume 169 of LIPIcs, pages 7:1–7:47, 2020. arXiv:1904.08914. https://doi.org/10.4230/LIPIcs.CCC.2020.7 arXiv:1904.08914 [2] A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. Earlier: FOCS'04, arXiv:quant-ph/0311001. https://doi.org/10.1137/S0097539705447311 arXiv:quant-ph/0311001 [3] A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang. Any AND-OR formula of size $N$ can be evaluated in time $N^{1/2+o(1)}$ on a quantum computer. SIAM Journal on Computing, 39(6):2513–2530, 2010. Earlier: FOCS'07. https://doi.org/10.1137/080712167 [4] A. Ambainis, L. Magnin, M. Rötteler, and J. Roland. Symmetry-assisted adversaries for quantum state generation. In Proc. of 26th IEEE CCC, pages 167–177, 2011. arXiv:1012.2112. https://doi.org/10.1109/CCC.2011.24 arXiv:1012.2112 [5] A. Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013. arXiv:1302.3143 [6] A. Belovs. Variations on quantum adversary. arXiv:1504.06943, 2015. arXiv:1504.06943 [7] A. Belovs. Global phase helps in quantum search: Yet another look at the welded tree problem. arXiv:2404.19476, 2024. arXiv:2404.19476 [8] A. Belovs, S. Jeffery, and D. Yolcu. Taming quantum time complexity. Quantum, 8:1444, 2024. arXiv:2311.15873. https://doi.org/10.22331/q-2024-08-23-1444 arXiv:2311.15873 [9] A. Belovs and T. Lee. Quantum algorithm for $k$-distinctness with prior knowledge on the input. arXiv:1108.3022, 2011. arXiv:1108.3022 [10] A. Belovs and A. Rosmanis. Tight quantum lower bound for approximate counting with quantum states. arXiv:2002.06879, 2020. arXiv:2002.06879 [11] A. Belovs and D. Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023. arXiv:2301.02003 [12] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. Earlier: STOC'93. https://doi.org/10.1137/S0097539796300921 [13] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation.
In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53–74, 2002. arXiv:quant-ph/0005055. arXiv:quant-ph/0005055 [14] H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In Proc. of 40th IEEE FOCS, pages 358–368, 1999. arXiv:cs/9904019. https://doi.org/10.1109/SFFCS.1999.814607 arXiv:cs/9904019 [15] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey.
Theoretical Computer Science, 288:21–43, 2002. https://doi.org/10.1016/S0304-3975(01)00144-X [16] A. M. Childs, R. Cleve, S. P. Jordan, and D. Yonge-Mallo. Discrete-query quantum algorithm for nand trees. Theory OF Computing, 5:119–123, 2009. arXiv:quant-ph/0702160. https://doi.org/10.4086/toc.2009.v005a005 arXiv:quant-ph/0702160 [17] A. Cornelissen, S. Jeffery, M. Ozols, and A. Piedrafita. Span programs and quantum time complexity. In Proc. of 45th MFCS, pages 26:1–26:14, 2020. arXiv:2005.01323. https://doi.org/10.4230/LIPIcs.MFCS.2020.26 arXiv:2005.01323 [18] P. G. Doyle and J. L. Snell. Random walks and electric networks, volume 22 of Carus Mathematical Monographs. MAA, 1984. arXiv:math.PR/0001057. arXiv:math.PR/0001057 [19] E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4:169–190, 2008. arXiv:quant-ph/0702144. https://doi.org/10.4086/toc.2008.v004a008 arXiv:quant-ph/0702144 [20] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proc. of 51st ACM STOC, pages 193–204, 2019. arXiv:1806.01838. https://doi.org/10.1145/3313276.3316366 arXiv:1806.01838 [21] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pages 212–219, 1996. arXiv:quant-ph/9605043. https://doi.org/10.1145/237814.237866 arXiv:quant-ph/9605043 [22] P. Høyer, T. Lee, and R. Špalek. Negative weights make adversaries stronger. In Proc. of 39th ACM STOC, pages 526–535, 2007. arXiv:quant-ph/0611054. https://doi.org/10.1145/1250790.1250867 arXiv:quant-ph/0611054 [23] T. Ito and S. Jeffery. Approximate span programs. Algorithmica, 81(6):2158–2195, 2019. arXiv:1507.00432. arXiv:1507.00432 [24] S. Jeffery. Span programs and quantum space complexity. Theory of Computing, 18(11):1–49, 2022. arXiv:1908.04232. https://doi.org/10.4086/toc.2022.v018a011 arXiv:1908.04232 [25] S. Jeffery. SIGACT News Complexity Theory Column 123: Composing quantum algorithms. ACM SIGACT News, 55(4):49–69, December 2024. [26] S. Jeffery and F. Witteveen. $\mathsf{QMA} = \mathsf{QMA}_1$ with an infinite counter. arXiv:2506.15551, 2025. arXiv:2506.15551 [27] S. Jeffery and S. Zur. Multidimensional quantum walks, with application to k-distinctness. In Proc. of 55th ACM STOC, pages 1125–1130, 2023. arXiv:2208.13492. https://doi.org/10.1145/3564246.3585158 arXiv:2208.13492 [28] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proc. of 52nd IEEE FOCS, pages 344–353, 2011. arXiv:1011.3020. https://doi.org/10.1109/FOCS.2011.75 arXiv:1011.3020 [29] G. H. Low and I. L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv:1707.05391, 2017. arXiv:1707.05391 [30] G. H. Low, T. J. Yoder, and I. L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6(4):041067, 2016. arXiv:1603.03996. https://doi.org/10.1103/PhysRevX.6.041067 arXiv:1603.03996 [31] C. Marriott and J. Watrous. Quantum Arthur–Merlin games. Computational Complexity, 14(2):122–152, 2005. Earlier: CCC'04, arXiv:cs/0506068. https://doi.org/10.1007/s00037-005-0194-x arXiv:cs/0506068 [32] D. Nagaj, P. Wocjan, and Y. Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11-12):1053–1068, 2009. arXiv:0904.1549. https://doi.org/10.5555/2012098.2012106 arXiv:0904.1549 [33] A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proc. of 31st ACM STOC, pages 384–393, 1999. arXiv:quant-ph/9804066. https://doi.org/10.1145/301250.301349 arXiv:quant-ph/9804066 [34] G. Pólya. Über eine aufgabe der wahrscheinlichkeitsrechnung betreffend die irrfahrt im straßennetz. Mathematische Annalen, 84(1):149–160, 1921. [35] P. Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5:566, 2021. arXiv:2103.09717. https://doi.org/10.22331/q-2021-10-19-566 arXiv:2103.09717 [36] B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. of 50th IEEE FOCS, pages 544–551, 2009. arXiv:0904.2759. https://doi.org/10.1109/FOCS.2009.55 arXiv:0904.2759 [37] B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8:291–319, 2012. Earlier: STOC'08, arXiv:0710.2630. https://doi.org/10.4086/toc.2012.v008a013 arXiv:0710.2630Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-23 12:23:47: Could not fetch cited-by data for 10.22331/q-2026-03-23-2039 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-23 12:23:48: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.