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 obtain the first nontrivial time-space lower bound for quantum algorithmssolving problems related to satisfiability. Our bound applies to MajSAT andMajMajSAT, which are complete problems for the first and second levels of thecounting hierarchy, respectively. We prove that for every real d and everypositive real epsilon there exists a real c>1 such that either: MajMajSAT doesnot have a quantum algorithm with bounded two-sided error that runs in timen^c, or MajSAT does not have a quantum algorithm with bounded two-sided errorthat runs in time n^d and space n^{1-\epsilon}. In particular, MajMajSAT cannotbe solved by a quantum algorithm with bounded two-sided error running in timen^{1+o(1)} and space n^{1-\epsilon} for any epsilon>0. The key technicalnovelty is a time- and space-efficient simulation of quantum computations withintermediate measurements by probabilistic machines with unbounded error. Wealso develop a model that is particularly suitable for the study of generalquantum computations with simultaneous time and space bounds. However, ourarguments hold for any reasonable uniform model of quantum computation.

A Quantum Time-Space Lower Bound for the Counting Hierarchy