Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.13339 · Quantum

Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

Matthew B. Hastings

Published Nov 11, 2019• 12 citations
arXivHTMLPDF

Abstract

We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden quench of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX- K -LIN 2 , for both even and odd K . The classical algorithm is a ``dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.

DOI
10.22331/q-2019-11-11-201

Related papers

Perspective on: Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

Nicholas Chancellor

•Jan 20, 2020•2 citations

Pretty good shadow tomography

Sabee Grewal, Angelos Pelecanos, Jack Spilecki +2 more

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.

quant-pharXiv:2610.06781•Oct 6, 2026•0 citations

Quantum SDP-Solvers: Better Upper and Lower Bounds

Joran van Apeldoorn, András Gilyén, Sander Gribling +1 more

Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•50 citations

Hybrid Quantum-classical Search Algorithms

Ansis Rosmanis

Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.

arXiv:2202.11443•ACM Transactions on Quantum Computing•Feb 16, 2024•12 citations

Introduction to Quantum Algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms. So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

arXiv:quant-ph/0005003•Apr 29, 2000•78 citations

When quantum and classical models disagree: learning beyond minimum norm least square

Slimane Thabet, Léo Monbroussou, Eliott Z. Mamon +1 more

Abstract Quantum Machine Learning algorithms based on Variational Quantum Circuits (VQCs) are important candidates for useful application of quantum computing. It is known that a VQC is a linear model in a feature space determined by its architecture. Such models can be compared to classical ones using various sets of tools, and surrogate models designed to classically approximate their results were proposed. At the same time, quantum advantages for learning tasks have been proven in the case of discrete data distributions and cryptography primitives. In this work, we propose a framework to avoid Random Feature approximation techniques. Using previous results, we establish conditions on the weight vectors of the quantum models that are necessary to avoid these dequantization methods. We show that this theory is compatible with previously proven quantum advantages on discrete inputs, and provides examples of advantages for continuous inputs. This separation is connected to large weight vector norm, and we suggest that this can only happen with a high dimensional feature map. Our results demonstrate that it is possible to design quantum models that cannot be classically approximated with good generalization. In addition, we provide a method to verify that the necessary condition is respected for a quantum model. Finally, we discuss how concentration issues must be considered to design such instances. We expect that our work will be a starting point to design near-term quantum models that avoid dequantization methods by ensuring non-classical convergence properties, and to identify existing quantum models that can be classically approximated.

arXiv:2411.04940•npj Quantum Information•Mar 27, 2026•1 citation
We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden quench of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX- K -LIN 2 , for both even and odd K . The classical algorithm is a ``dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.
We give a shadow tomography algorithm that uses O(log⁡(m)log⁡(m/δ)/ε2)O(\log(m) \log(m/δ) / \varepsilon^2)O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state ρρρ and observables O1,…,OmO_1,\ldots,O_mO1​,…,Om​, the algorithm outputs estimates of tr(Oiρ)\mathrm{tr}(O_iρ)tr(Oi​ρ) for all i∈[m]i\in[m]i∈[m] that are all accurate to within ±ε\pm\varepsilon±ε, except with probability at most δδδ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log⁡(m)/ε2)O(\log(m)/\varepsilon^2)O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log⁡(m)\log(m)log(m) factor separating the complexity of the quantum problem from its classical counterpart.
Brandao and Svore recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when m is approximately n, which is the same as classical.
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.
Abstract Quantum Machine Learning algorithms based on Variational Quantum Circuits (VQCs) are important candidates for useful application of quantum computing. It is known that a VQC is a linear model in a feature space determined by its architecture. Such models can be compared to classical ones using various sets of tools, and surrogate models designed to classically approximate their results were proposed. At the same time, quantum advantages for learning tasks have been proven in the case of discrete data distributions and cryptography primitives. In this work, we propose a framework to avoid Random Feature approximation techniques. Using previous results, we establish conditions on the weight vectors of the quantum models that are necessary to avoid these dequantization methods. We show that this theory is compatible with previously proven quantum advantages on discrete inputs, and provides examples of advantages for continuous inputs. This separation is connected to large weight vector norm, and we suggest that this can only happen with a high dimensional feature map. Our results demonstrate that it is possible to design quantum models that cannot be classically approximated with good generalization. In addition, we provide a method to verify that the necessary condition is respected for a quantum model. Finally, we discuss how concentration issues must be considered to design such instances. We expect that our work will be a starting point to design near-term quantum models that avoid dequantization methods by ensuring non-classical convergence properties, and to identify existing quantum models that can be classically approximated.