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

In this paper, we introduce a new public quantum interactive proof system andthe first quantum alternating Turing machine: qAM proof system and qATM,respectively. Both are obtained from their classical counterparts(Arthur-Merlin proof system and alternating Turing machine, respectively,) byaugmenting them with a fixed-size quantum register. We focus on space-boundedcomputation, and obtain the following surprising results: Both of them withconstant-space are Turing-equivalent. More specifically, we show that for anyTuring-recognizable language, there exists a constant-space weak-qAM system,(the nonmembers do not need to be rejected with high probability), and we showthat any Turing-recognizable language can be recognized by a constant-spaceqATM even with one-way input head.  For strong proof systems, where the nonmembers must be rejected with highprobability, we show that the known space-bounded classical private protocolscan also be simulated by our public qAM system with the same space bound.Besides, we introduce a strong version of qATM: The qATM that must halt inevery computation path. Then, we show that strong qATMs (similar to privateATMs) can simulate deterministic space with exponentially less space. Thisleads to shifting the deterministic space hierarchy exactly by one-level. Themethod behind the main results is a new public protocol cleverly using itsfixed-size quantum register. Interestingly, the quantum part of this publicprotocol cannot be simulated by any space-bounded classical protocol in somecases.

Turing-equivalent automata using a fixed-size quantum memory