On Query-to-Communication Lifting for Adversary Bounds
- URL: http://arxiv.org/abs/2012.03415v1
- Date: Mon, 7 Dec 2020 02:10:37 GMT
- Title: On Query-to-Communication Lifting for Adversary Bounds
- Authors: Anurag Anshu, Shalev Ben-David, Srijita Kundu
- Abstract summary: We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget.
We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree.
- Score: 14.567067583556714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate query-to-communication lifting theorems for models related to
the quantum adversary bounds. Our results are as follows:
1. We show that the classical adversary bound lifts to a lower bound on
randomized communication complexity with a constant-sized gadget. We also show
that the classical adversary bound is a strictly stronger lower bound technique
than the previously-lifted measure known as critical block sensitivity, making
our lifting theorem one of the strongest lifting theorems for randomized
communication complexity using a constant-sized gadget.
2. Turning to quantum models, we show a connection between lifting theorems
for quantum adversary bounds and secure 2-party quantum computation in a
certain "honest-but-curious" model. Under the assumption that such secure
2-party computation is impossible, we show that a simplified version of the
positive-weight adversary bound lifts to a quantum communication lower bound
using a constant-sized gadget. We also give an unconditional lifting theorem
which lower bounds bounded-round quantum communication protocols.
3. Finally, we give some new results in query complexity. We show that the
classical adversary and the positive-weight quantum adversary are quadratically
related. We also show that the positive-weight quantum adversary is never
larger than the square of the approximate degree. Both relations hold even for
partial functions.
Related papers
- QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
There are problems for which there is no trivial' computational advantage possible with the current quantum hardware.
We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity?
By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
arXiv Detail & Related papers (2023-09-28T13:30:20Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
We study the query complexity of Boolean functions under general higher order quantum computations.
We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity.
We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
arXiv Detail & Related papers (2023-07-18T13:12:55Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical.
We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more.
Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Commitments to Quantum States [11.217084610985674]
A commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view.
We show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages.
Commitments to quantum states open the door to many new cryptographic possibilities.
arXiv Detail & Related papers (2022-10-11T04:34:36Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems.
Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
arXiv Detail & Related papers (2021-09-06T14:35:15Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model.
This yields the first post-quantum succinct argument system from any falsifiable assumption.
arXiv Detail & Related papers (2021-03-15T05:09:17Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel.
We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries.
We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
arXiv Detail & Related papers (2020-10-15T17:55:31Z) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse.
We show that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value.
We provide evidence that the 0.91 result is the best possible using a large class of proof strategies.
arXiv Detail & Related papers (2018-09-25T22:39:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.