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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Fine-grained quantum supremacy is a study of proving (nearly) tight timelower bounds for classical simulations of quantum computing under "fine-grainedcomplexity" assumptions. We show that under conjectures on Orthogonal Vectors(OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong andweak classical simulations of quantum computing are impossible in certainexponential time with respect to the number of qubits. Those conjectures arewidely used in classical fine-grained complexity theory in which polynomialtime hardness is conjectured. All previous results of fine-grained quantumsupremacy are based on ETH, SETH, or their variants that are conjectures forSAT in which exponential time hardness is conjectured. We show that there existquantum circuits which cannot be classically simulated in certain exponentialtime with respect to the number of qubits first by considering a Quantum RandomAccess Memory (QRAM) based quantum computing model and next by considering anon-QRAM model quantum computation. In the case of the QRAM model, the size ofquantum circuits is linear with respect to the number of qubits and in the caseof the non-QRAM model, the size of the quantum circuits is exponential withrespect to the number of qubits but the results are still non-trivial.

Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths