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.
The quantum state discrimination problem has Alice sending a quantum state to Bob who wins if he correctly identifies the state. The pretty good measurement, also known as the square root measurement, performs pretty well at this task. We study the version of this problem where Bob tries to lose with the greatest probability possible (which is harder than it sounds). We define the pretty bad measurement, which performs pretty well at this task, or in other words, pretty poorly for the original task. We show that both the pretty good measurement and the pretty bad measurement are always no worse than blind guessing at their respective tasks. As an application, we apply the pretty bad measurement to the quantum state anomaly detection problem and show how to avoid pretty bad qubits.
We derive a new lower bound on the success probability of the Pretty Good Measurement (PGM) for worst-case quantum state discrimination among
m pure states. Our bound is strictly tighter than the previously known Gram-matrix-based bound for
m≥4. The proof adapts techniques from Barnum and Knill's analysis of the average-case PGM, applied here to the worst-case scenario. By comparing the PGM to the sequential measurement algorithm, we obtain a guarantee showing that, in the low-fidelity regime, the PGM's success probability decreases quadratically with respect to the maximum pairwise overlap, rather than linearly as in earlier bounds.
We give a shadow tomography algorithm that uses
O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state
ρ and observables
O1,…,Om, the algorithm outputs estimates of
tr(Oiρ) for all
i∈[m] that are all accurate to within
±ε, 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) 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.