- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Sampling from certain distributions is believed to be inefficient classically yet efficient for quantum computers. This has led sampling problems to become a leading proposal for demonstrating quantum computers performing a task beyond what efficient classical algorithms can achieve, sometimes known as "quantum supremacy." Proofs of classical hardness in many of these quantum supremacy proposals rely on demonstrating the "anti-concentration" of the distribution in question, which allows one to leverage existing complexity theory results to show classical hardness conditioned on reasonable complexity theory conjectures. The authors of this work note that anti-concentration is similar to a phenomenon widely studied in the quantum machine learning literature: loss concentration, otherwise known as barren plateaus. The authors formally compute, for three examples, whether the distribution in question anti-concentrates and whether training objectives based on either the MMD or SD loss exhibit loss concentration. The authors then end with numerical simulations to validate these properties.
Critical strengths
What I found most surprising about this work was the authors showing how loss concentration can substantially differ between the MMD and SD loss functions, and also how loss concentration under either of these objectives does not necessarily imply anti-concentration. The authors' results lead them to suggest that sampling problems with "peaked" distributions might be viable candidates as machine learning problems that are both classically hard and quantumly easy. This echoes some other recent results in the field (which the authors cite) proposing biased quantum models as quantum learning algorithms, and provides nice theoretical backing to these prior observations.
Critical weaknesses
The distributions the authors consider are fairly specific: one is a product distribution with no correlations, one heavily inspired by the random circuit sampling experiments which motivated the anti-concentration property to begin with, and the final inspired by proposals for verifiable quantum supremacy experiments. It would have been nice to see a concrete statement linking loss concentration and anti-concentration for more general choices of loss function, or otherwise showing results for distributions which haven't already been extensively studied in the quantum supremacy literature. I do acknowledge that the authors' numerical results do go further than their analytic results by investigating circuit classes like IQP circuits and MPS distributions, which mitigates this weakness.
Additionally, as the authors state, anti-concentration does not actually indicate hardness generally. In other words, while the results of this paper are useful heuristics guiding further development, they do not explicitly show a link between classical hardness and training complexity.
In short, the main weaknesses of the work are the narrow scope of their theoretical analyses; overall, I think this weakness is outweighed by the strengths of the work, and I recommend acceptance.
Questions for authors
Do the authors believe their techniques generalize to other distributions beyond what's already currently seen in the quantum supremacy literature? For instance, what is the barrier to using these methods to study MPSs, which the authors only look at numerically? I imagine at low bond dimension the results would mirror the authors' product distribution results and would provide a nice analytic generalization.
The authors state on page 6: "There exists a compact representation of the circuit, implying a loss function sensitive to it"; I didn't follow this. What do the authors mean by this?
Response to all reviewers and changes
We would like to once again thank all referees for their effort and time. We just uploaded a revised version of the manuscript with further context and discussion, factoring in the comments, which we believe significantly improved the manuscript. For simplicity, we list the changes below.
We hope the changes help clarify the referees' doubts. We are happy to answer any further questions until the discussion period ends.
We have also given a comparative document of old and new versions with highlighted changes in the supplementary material.