English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a quantum sample-to-query lifting theorem. It reveals a quadraticrelation between quantum sample and query complexities regarding quantumproperty testing, which is optimal and saturated by quantum statediscrimination. Based on it, we provide a new method for proving lower boundson quantum query algorithms from an information theory perspective. Using thismethod, we prove the following new results:  1. A matching lower bound $\widetilde \Omega(\beta)$ for quantum Gibbssampling at inverse temperature $\beta$, showing that the quantum Gibbs samplerby Gily\'en, Su, Low, and Wiebe (2019) is optimal.  2. A new lower bound $\widetilde \Omega(1/\sqrt{\Delta})$ for theentanglement entropy problem with gap $\Delta$, which was recently studied byShe and Yuen (2023).  In addition, we also provide unified proofs for some known lower bounds thathave been proven previously via different techniques, including those forphase/amplitude estimation and Hamiltonian simulation.

Quantum Lower Bounds by Sample-to-Query Lifting