Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics

Area of Science:

• Quantum Information Science
• Computational Complexity Theory
• Condensed Matter Physics

Background:

• Demonstrating quantum computational speed-up is vital for near-term quantum technology.
• Sampling protocols for quantum simulators offer potential quantum advantage but require rigorous theoretical analysis.
• Previous schemes like boson sampling face challenges with assumptions and theoretical loopholes.

Purpose of the Study:

• To rigorously prove two open conjectures for a quantum simulator sampling protocol.
• To establish the anticoncentration of generated probability distributions.
• To prove the average-case hardness of exactly evaluating these probabilities.

Main Methods:

• Utilizing insights from approximate 2-designs for unitary groups to prove anticoncentration.
• Developing new techniques to show 2D time evolution generates approximate 2-designs.
• Leveraging recent advancements in random circuit sampling for average-case hardness proofs.

Main Results:

• The study rigorously proves anticoncentration of probability distributions for the sampling protocol.
• Average-case hardness of probability evaluation is established, building on random circuit sampling techniques.
• The 2D time evolution of the Ising Hamiltonian protocol is shown to yield approximate 2-designs.

Conclusions:

• This work provides the strongest theoretical evidence to date for the classical intractability of Hamiltonian quantum simulators.
• The findings strengthen the case for quantum advantage in near-term quantum computing.
• The rigorous proofs address key theoretical challenges in quantum sampling protocols.