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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We investigate the connection between interference and computational powerwithin the operationally defined framework of generalised probabilistictheories. To compare the computational abilities of different theories withinthis framework we show that any theory satisfying three natural physicalprinciples possess a well-defined oracle model. Indeed, we prove a subroutinetheorem for oracles in such theories which is a necessary condition for theoracle to be well-defined. The three principles are: causality (roughly, nosignalling from the future), purification (each mixed state arises as themarginal of a pure state of a larger system), and strong symmetry existence ofnon-trivial reversible transformations). Sorkin has defined a hierarchy ofconceivable interference behaviours, where the order in the hierarchycorresponds to the number of paths that have an irreducible interaction in amulti-slit experiment. Given our oracle model, we show that if a classicalcomputer requires at least n queries to solve a learning problem, then thecorresponding lower bound in theories lying at the kth level of Sorkin'shierarchy is n/k. Hence, lower bounds on the number of queries to a quantumoracle needed to solve certain problems are not optimal in the space of allgeneralised probabilistic theories, although it is not yet known whether theoptimal bounds are achievable in general. Hence searches for higher-orderinterference are not only foundationally motivated, but constitute a search fora computational resource beyond that offered by quantum computation.

Oracles and query lower bounds in generalised probabilistic theories