Classical simulation of one-query quantum distinguishers

Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C. S. Lui

TL;DR

This paper investigates how well classical algorithms can "imitate" quantum algorithms that make a single query to an oracle. The authors show that classical algorithms can achieve a significant fraction of the advantage of these quantum distinguishers, but only if they are allowed more queries or multiple rounds of queries. This work provides a deeper understanding of the power of limited quantum computation and its relationship to classical query complexity.

What Problem Does This Paper Address?

The field of quantum computing promises significant speedups for certain computational tasks. However, fully capable quantum computers are still a long way off. This raises a crucial question: what can we do with "limited" quantum devices, and how does their power compare to classical computers? This paper focuses on a specific aspect: quantum "distinguishers" that make only one query to an oracle. A distinguisher is an algorithm designed to tell apart two different probability distributions. The authors want to understand the classical "cost" (in terms of queries and rounds) of simulating the advantage a one-query quantum distinguisher has. Specifically, they ask: if a quantum algorithm can tell apart two distributions with a certain advantage using just one query, how many queries and rounds would a classical algorithm need to achieve a similar advantage? This is important for understanding the security of cryptographic systems against quantum adversaries and for designing efficient quantum algorithms.

Methods

The core of the paper involves developing and analyzing classical algorithms that simulate one-query quantum distinguishers. The authors build upon existing work, particularly a construction by Aaronson and Ambainis, which shows a separation between quantum and classical query complexity.

Key techniques include:

  • Unbiased Estimators: The authors construct classical algorithms that act as "unbiased estimators" for the advantage of a quantum distinguisher. This means their output, on average, matches the quantum advantage.
  • Grothendieck's Inequality and Factorization: This powerful mathematical tool is used to relate different norms of matrices, which is crucial for bounding the performance of the classical estimators. It helps bridge the gap between the abstract properties of quantum algorithms and the concrete performance of classical ones.
  • Non-adaptive and Adaptive Classical Algorithms: The paper analyzes both types of classical algorithms. Non-adaptive algorithms make all their queries in one go, while adaptive algorithms can adjust their subsequent queries based on the results of previous ones. The latter are generally more powerful.
  • Truncation and Variance Analysis: To ensure the classical algorithms produce outputs in the required range and to bound their performance, techniques like truncating outputs and analyzing the variance of estimators are employed.
  • Gaussian Distribution Analysis: The paper leverages properties of Gaussian distributions and their KL-divergence to analyze the advantage of two-round classical algorithms.

Datasets

Not discussed in the paper. The paper deals with theoretical constructs (probability distributions and oracles) rather than empirical datasets.

Key Insights and Ideas

  • Classical Simulation is Surprisingly Powerful (with caveats): Even with a single quantum query, classical algorithms can achieve a significant fraction of the quantum advantage, but this requires more queries or multiple rounds. This suggests that the "quantum advantage" for one-query algorithms isn't as dramatic as it might initially seem when considering classical simulation.
  • Adaptive vs. Non-adaptive: The paper shows that adaptive classical algorithms (which can use information from previous queries to guide future ones) offer a better simulation advantage than non-adaptive ones, especially in the context of two-round algorithms.
  • Tight Bounds: The authors strive to provide "tight" bounds, meaning their upper bounds on classical simulation performance are close to known lower bounds, suggesting their results are close to optimal.
  • Connection to Statistical Estimation: The problem of simulating quantum distinguishers is framed in terms of statistical estimation, where classical algorithms try to estimate a quantity related to the quantum advantage.

Key Results

The paper presents several key theoretical results, summarized in Table 1:

  • Non-adaptive Classical Simulation: A one-query quantum distinguisher with advantage $\epsilon$ can be simulated by a $k$-query non-adaptive classical distinguisher with advantage $\Omega(\epsilon k / \sqrt{n})$ or $\Omega(\epsilon^2 k^2 / n)$ (for $k=O(\sqrt{n})$).
  • Two-Round Adaptive Classical Simulation: A one-query quantum distinguisher with advantage $\epsilon$ can be simulated by a $2k$-query two-round adaptive classical distinguisher with advantage $\Omega(\epsilon^2 k / \sqrt{n} \log n)$.
  • Optimality: The paper demonstrates that these bounds are nearly optimal, particularly for the two-round adaptive case, up to logarithmic factors.

Limitations and Future Work

  • Open Question on Adaptivity: While the paper shows adaptive algorithms are better for two-round simulations, it remains an open question whether adaptivity offers a significant advantage in classical simulations of one-query quantum distinguishers in general.
  • Constant Factors: The results are often stated up to constant factors, which is typical in theoretical computer science but might be relevant for practical implementations.
  • Generalization to More Quantum Queries: The paper focuses specifically on one-query quantum distinguishers. Extending these results to quantum distinguishers with more queries would be a natural next step.
  • Specific Quantum Algorithms: The results are "black-box" in the sense that they apply to any one-query quantum distinguisher. Investigating the simulation of specific, known quantum algorithms would be valuable.

Summary updated

BibTeX
@article{bogdanov2023classical,
  author = {Andrej Bogdanov and TsunMing Cheung and Krishnamoorthy Dinesh and John C. S. Lui},
  title = {{Classical simulation of one-query quantum distinguishers}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2023},
  url = {https://openreview.net/forum?id=rWpJQ8Yn1r},
}
Figure