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

The classical Goldreich-Levin (G-L) theorem is presented as a block-box query prob­ lem, referred to herein as the G-L problem. The query complexity of this problem is bounded in both classical and quantum settings. The well-known upper bound of the classical G-L problem is analyzed in a pedagogical manner. A proof of the lower bound of the classical G-L problem is given using the techniques of classical information theory. This classical analysis is then extended to the realm of quantum computing by noting the similarity of the noiseless G-L problem to the inner-product query problem solved by the quantum circuit defined by Bernstein and Vazirani (B­ V). An upper bound of the query complexity of the quantum G-L problem is proven by extension of the B-V circuit to incorporate noisy inner-product queries. The lower bound of the query complexity of the quantum G-L problem is proven by adapting the proof of the optimality of the quantum search algorithm to include modified inner-product queries. Both the classical and quantum versions of the Goldreich-Levin theorem have cryptographic applications in the area of bit commitment. A discussion of the im­ possibility of unconditional quantum bit commitment is followed by the presentation of both classical and quantum bit commitment protocols that are based on the as­ sumption of the existence of classical and quantum one-way permutations. The relative security of the classical and quantum protocols are compared where it is shown that the quantum version is quantitatively more secure.

The classical and quantum complexity of the Goldreich-Levin problem with applications to bit commitment