quantum-computing

Assessing fault-tolerant quantum advantage for $k$-SAT with structure

Quantum Science and Technology (arXiv overlay)

15 min read

0 likes

⚡ Quantum Brief

Researchers Brehm and Weggemans evaluated quantum algorithms (Backtracking and Grover) against the 2023 SAT competition winner for structured $k$-SAT problems, using hybrid benchmarking and fault-tolerant metrics. Quantum speedups largely disappear when minimal problem structure is introduced or when $T$-count (not $T$-depth) is used, even asymptotically, challenging prior worst-case theoretical advantages. Only Grover’s algorithm shows potential to outperform classical solvers—but solely in a narrow regime, using $T$-depth, and only for single-day runtime constraints. The study confirms earlier unstructured-case results but reveals practical quantum advantage remains elusive for industry-relevant $k$-SAT instances due to error-correction overheads. Sophisticated heuristics might restore asymptotic scaling for quantum backtracking, but near-term practical speedups appear limited for structured problems.

Assessing fault-tolerant quantum advantage for $k$-SAT with structure

Summarize this article with:

AbstractFor many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overlooks significant overheads due to error correction and the fact that real-world instances often contain exploitable structure. In this work, we employ the hybrid benchmarking method to evaluate the potential of quantum Backtracking and Grover's algorithm against the 2023 SAT competition main track winner in solving random $k$-SAT instances with tunable structure, designed to represent industry-like scenarios, using both $T$-depth and $T$-count as cost metrics to estimate quantum run times. Our findings reproduce the results of Campbell, Khurana, and Montanaro (Quantum '19) in the unstructured case using hybrid benchmarking. However, we offer a more sobering perspective in practically relevant regimes: almost all quantum speedups vanish, even asymptotically, when minimal structure is introduced or when $T$-count is considered instead of $T$-depth. Moreover, when the requirement is for the algorithm to find a solution within a single day, we find that only Grover's algorithm has the potential to outperform classical algorithms, but only in a very limited regime and only when using $T$-depth. We also discuss how more sophisticated heuristics could restore the asymptotic scaling advantage for quantum backtracking, but our findings suggest that the potential for practical quantum speedups in more structured $k$-SAT solving will remain limited.► BibTeX data@article{Brehm2026assessingfault, doi = {10.22331/q-2026-01-20-1975}, url = {https://doi.org/10.22331/q-2026-01-20-1975}, title = {Assessing fault-tolerant quantum advantage for {$k$}-{SAT} with structure}, author = {Brehm, Martijn and Weggemans, Jordi}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1975}, month = jan, year = {2026} }► References [1] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel Egger, Bruce Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, and Christa Zoufal. Challenges and opportunities in quantum optimization.

Nature Reviews Physics, 6, 10 2024. 10.1038/s42254-024-00770-9. https://doi.org/10.1038/s42254-024-00770-9 [2] All the data used in this paper, and all the code used to generate this data, can be found in the following repository. URL https://github.com/martijnmartijnmartijnmartijn/Quantum-advantage-k-SAT-with-structure. https://github.com/martijnmartijnmartijnmartijn/Quantum-advantage-k-SAT-with-structure [3] Tasniem Nasser Alyahya, Mohamed El Bachir Menai, and Hassan Mathkour. On the structure of the boolean satisfiability problem: A survey. ACM Comput. Surv., 55 (3), mar 2022. ISSN 0360-0300. 10.1145/3491210. https://doi.org/10.1145/3491210 [4] Andris Ambainis and Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 989–1002, 2017. 10.1145/3055399.3055444. https://doi.org/10.1145/3055399.3055444 [5] Sabrina Ammann, Maximilian Hess, Debora Ramacciotti, Sándor P Fekete, Paulina LA Goedicke, David Gross, Andreea Lefterovici, Tobias J Osborne, Michael Perk, Antonio Rotundo, et al. Realistic runtime analysis for quantum simplex computation, 2023. [6] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX quantum, 2 (1): 010103, 2021. 10.1103/PRXQuantum.2.010103. https://doi.org/10.1103/PRXQuantum.2.010103 [7] Aleksandrs Belovs. Quantum walks and electric networks, 2013. [8] Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020. In Proc. of SAT Competition 2020 – Solver and Benchmark Descriptions, volume B-2020-1 of Department of Computer Science Report Series B, pages 51–53. University of Helsinki, 2020. 10138/318754. [9] Armin Biere, Tobias Faller, Katalin Fazekas, Mathias Fleury, Nils Froleyks, and Florian Pollitt. CaDiCaL 2.0.

In Arie Gurfinkel and Vijay Ganesh, editors, Computer Aided Verification - 36th International Conference, CAV 2024, Montreal, QC, Canada, July 24-27, 2024, Proceedings, Part I, volume 14681 of Lecture Notes in Computer Science, pages 133–152. Springer, 2024. 10.1007/978-3-031-65627-9_7. https://doi.org/10.1007/978-3-031-65627-9_7 [10] Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. Quantifying Grover speed-ups beyond asymptotic analysis. Quantum, 7: 1133, oct 2023. ISSN 2521-327X. 10.22331/q-2023-10-10-1133. https://doi.org/10.22331/q-2023-10-10-1133 [11] Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. Quantum algorithms for community detection and their empirical run-times. Quantum Information and Computation, 24 (5&6): 0361–0410, 2024. 10.26421/QIC24.5-6-1. https://doi.org/10.26421/QIC24.5-6-1 [12] Earl Campbell, Ankur Khurana, and Ashley Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3: 167, jul 2019. ISSN 2521-327X. 10.22331/q-2019-07-18-167. https://doi.org/10.22331/q-2019-07-18-167 [13] Peter Cheeseman, Bob Kanefsky, and William M. Taylor. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI'91, page 331–337, San Francisco, CA, USA, 1991.

Morgan Kaufmann Publishers Inc. ISBN 1558601600. [14] Martin Davis and Hilary Putnam. A computing procedure for quantification theory. J. ACM, 7 (3): 201–215, jul 1960. ISSN 0004-5411. 10.1145/321033.321034. https://doi.org/10.1145/321033.321034 [15] Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving. Commun. ACM, 5 (7): 394–397, jul 1962. ISSN 0001-0782. 10.1145/368273.368557. https://doi.org/10.1145/368273.368557 [16] Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, STOC '15, pages 59–68. ACM, 2015. 10.1145/2746539.2746619. https://doi.org/10.1145/2746539.2746619 [17] W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, and R.E. Kooij. Effective graph resistance. Linear Algebra and its Applications, 435 (10): 2491–2506, 2011. ISSN 0024-3795. https://doi.org/10.1016/j.laa.2011.02.024. Special Issue in Honor of Dragos Cvetkovic. https://doi.org/10.1016/j.laa.2011.02.024 [18] Austin G Fowler. Time-optimal quantum computation, 2012. [19] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, 2012. 10.1103/PhysRevA.86.032324. https://doi.org/10.1103/PhysRevA.86.032324 [20] John Franco and John Martin. Chapter 1. A History of Satisfiability.

Effective Auxiliary Variables via Structured Reencoding. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), volume 271 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:19, 2023. 10.4230/LIPIcs.SAT.2023.11. https://doi.org/10.4230/LIPIcs.SAT.2023.11 [24] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62 (2): 367–375, mar 2001. 10.1006/jcss.2000.1727. https://doi.org/10.1006/jcss.2000.1727 [25] Michael Jarret and Kianna Wan. Improved quantum backtracking algorithms using effective resistance estimates. Phys. Rev. A, 97: 022337, feb 2018. 10.1103/PhysRevA.97.022337. https://doi.org/10.1103/PhysRevA.97.022337 [26] Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38 (3): 963–981, 2008. 10.1137/050644756. https://doi.org/10.1137/050644756 [27] Joao Marques-Silva, Ines Lynce, and Sharad Malik. Chapter 4. Conflict-Driven Clause Learning SAT Solvers.

In Armin Biere, Marijn Heule, Hans Van Maaren, and Toby Walsh, editors, Frontiers in Artificial Intelligence and Applications. IOS Press, February 2021. ISBN 978-1-64368-160-3 978-1-64368-161-0. 10.3233/FAIA200987. https://doi.org/10.3233/FAIA200987 [28] Milan Merkle. Jensen's inequality for medians. Statistics & probability letters, 71 (3): 277–281, 2005. 10.1016/j.spl.2004.11.010. https://doi.org/10.1016/j.spl.2004.11.010 [29] Ashley Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14 (15): 1–24, 2018. 10.4086/toc.2018.v014a015. https://doi.org/10.4086/toc.2018.v014a015 [30] Ramamohan Paturi, Pavel Pudlák, and Francis Zane. Satisfiability coding lemma. In 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19-22, 1997, pages 566–574. IEEE Computer Society, oct 1997. 10.1109/SFCS.1997.646146. https://doi.org/10.1109/SFCS.1997.646146 [31] Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for $k$-sat. J. ACM, 52 (3): 337–364, may 2005. ISSN 0004-5411. 10.1145/1066100.1066101. https://doi.org/10.1145/1066100.1066101 [32] Stephen Piddock. Quantum walk search algorithms and effective resistance, 2019. [33] Uwe Schöning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 410–414. IEEE Computer Society, oct 1999. 10.1109/SFFCS.1999.814612. https://doi.org/10.1109/SFFCS.1999.814612 [34] Peter Selinger. Quantum circuits of $t$-depth one. Phys. Rev. A, 87: 042302, apr 2013. 10.1103/PhysRevA.87.042302. https://doi.org/10.1103/PhysRevA.87.042302 [35] Mario Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Symposium on Foundations of Computer Science, FOCS 2004, Rome, Italy, October 17-19, 2004, Proceedings, FOCS '04, pages 32–41. IEEE Computer Society, 2004. 10.1109/FOCS.2004.53. https://doi.org/10.1109/FOCS.2004.53 [36] Zewen Zhang, Roger Paredes, Bhuvanesh Sundar, David Quiroga, Anastasios Kyrillidis, Leonardo Duenas-Osorio, Guido Pagano, and Kaden RA Hazzard. Grover-qaoa for 3-sat: Quadratic speedup, fair-sampling, and parameter clustering. Quantum Science and Technology, 10 (1): 015022, 2024. 10.1088/2058-9565/ad895c. https://doi.org/10.1088/2058-9565/ad895cCited byCould not fetch Crossref cited-by data during last attempt 2026-01-20 11:21:02: Could not fetch cited-by data for 10.22331/q-2026-01-20-1975 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-20 11:21:03: 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. AbstractFor many problems, quantum algorithms promise speedups over their classical counterparts. However, these results predominantly rely on asymptotic worst-case analysis, which overlooks significant overheads due to error correction and the fact that real-world instances often contain exploitable structure. In this work, we employ the hybrid benchmarking method to evaluate the potential of quantum Backtracking and Grover's algorithm against the 2023 SAT competition main track winner in solving random $k$-SAT instances with tunable structure, designed to represent industry-like scenarios, using both $T$-depth and $T$-count as cost metrics to estimate quantum run times. Our findings reproduce the results of Campbell, Khurana, and Montanaro (Quantum '19) in the unstructured case using hybrid benchmarking. However, we offer a more sobering perspective in practically relevant regimes: almost all quantum speedups vanish, even asymptotically, when minimal structure is introduced or when $T$-count is considered instead of $T$-depth. Moreover, when the requirement is for the algorithm to find a solution within a single day, we find that only Grover's algorithm has the potential to outperform classical algorithms, but only in a very limited regime and only when using $T$-depth. We also discuss how more sophisticated heuristics could restore the asymptotic scaling advantage for quantum backtracking, but our findings suggest that the potential for practical quantum speedups in more structured $k$-SAT solving will remain limited.► BibTeX data@article{Brehm2026assessingfault, doi = {10.22331/q-2026-01-20-1975}, url = {https://doi.org/10.22331/q-2026-01-20-1975}, title = {Assessing fault-tolerant quantum advantage for {$k$}-{SAT} with structure}, author = {Brehm, Martijn and Weggemans, Jordi}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1975}, month = jan, year = {2026} }► References [1] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel Egger, Bruce Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, and Christa Zoufal. Challenges and opportunities in quantum optimization.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Assessing fault-tolerant quantum advantage for $k$-SAT with structure

Tags

Source Information