Certificate Games and Consequences for the Classical Adversary Bound

• URL: http://arxiv.org/abs/2211.03396v3
• Date: Mon, 10 Mar 2025 20:14:40 GMT
• Title: Certificate Games and Consequences for the Classical Adversary Bound
• Authors: Sourav Chakraborty, Anna Gál, Mika Göös, Sophie Laplante, Rajat Mittal, Anupa Sunny,
• Abstract summary: We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games.<n>The quantum measure reveals an interesting and surprising difference between classical and quantum query models.
• Score: 3.11717505289722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting. We study four versions of certificate games, namely private coin, public coin, shared entanglement and non-signaling games. The public-coin variant of certificate games gives a new characterization of the classical adversary bound, a lower bound on randomized query complexity which was introduced as a classical version of the quantum (non-negative) quantum adversary bound. We show that complexity in the public coin model (therefore also the classical adversary) is bounded above by certificate complexity, as well as by expectational certificate complexity and sabotage complexity. On the other hand, it is bounded below by fractional and randomized certificate complexity. The quantum measure reveals an interesting and surprising difference between classical and quantum query models: the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of $n$ on the quantum certificate game complexity of the OR function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on to show that this ``non-signaling bottleneck'' applies to all functions with high sensitivity, block sensitivity, fractional block sensitivity, as well as classical adversary. This implies the collapse of all models of certificate games, except private randomness, to the classical adversary bound. We consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1, and give a new characterization of sensitivity and spectral sensitivity.

Related papers

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  We show structural results for p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE. Surprisingly, our findings uncover relationships that diverge from their classical analogues. For applications, we address interesting questions in quantum cryptography, quantum property testing, and unitary synthesis.
  arXiv  Detail & Related papers  (2024-11-06T07:29:52Z)
• Quantum complexity and localization in random quantum circuits [0.0]
  We study complexity in random quantum circuits with and without measurements. For $N$ qubits without measurements, the saturation value scales as $2N-1$, and the saturation time scales as $2N$. We observe that complexity acts as a novel probe of Anderson localization and many-body localization.
  arXiv  Detail & Related papers  (2024-09-05T16:10:54Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Learning quantum states and unitaries of bounded gate complexity [2.034135396070497]
  We prove that to learn a state generated by a quantum circuit with $G$ two-qubit gates to a small trace distance, a sample complexity scaling linearly in $G$ is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by $G$ gates to a small average-case error scales linearly in $G$.
  arXiv  Detail & Related papers  (2023-10-30T18:00:03Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  We numerically simulate and characterize the operation of various quantum processors. We identify and assess quantum complexity by comparing the performance of each device against benchmark lines. We find that the majorization-based benchmark holds as long as the circuits' output states have, on average, high purity.
  arXiv  Detail & Related papers  (2023-04-10T23:01:10Z)
• 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)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• Verifiable Quantum Advantage without Structure [15.701707809084716]
  We replace a random oracle with a concrete cryptographic hash function such as SHA2. We obtain plausible Minicrypt instantiations of the above results.
  arXiv  Detail & Related papers  (2022-04-05T08:58:24Z)
• On query complexity measures and their relations for symmetric functions [0.0]
  We show how to give lower bounds on quantum query complexity using Boolean and adversary methods. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. We show how large certificate complexity and block sensitivity can be as compared to sensitivity for symmetric functions.
  arXiv  Detail & Related papers  (2021-10-25T02:55:39Z)
• Straddling-gates problem in multipartite quantum systems [20.428960719376164]
  We study a variant of quantum circuit complexity, the binding complexity. We show that any $m$partite Schmidt decomposable state has binding complexity linear in $m$, which hints its multi-separable property.
  arXiv  Detail & Related papers  (2021-10-13T16:28:12Z)
• 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)
• 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)
• Quantum Go Machine [15.33065067850941]
  We experimentally demonstrate a quantum version of Go using correlated photon pairs entangled in polarization degree of freedom. Some quantum resources, like coherence or entanglement, can also be encoded to represent the state of quantum stones. Our results establish a paradigm of inventing new games with quantum-enabled difficulties.
  arXiv  Detail & Related papers  (2020-07-23T18:00:01Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
  The paper studies theoretic aspects of quantum refereed games. The abstract games are between two competing players that send quantum states to a referee. The referee performs an efficiently implementable joint measurement on the two states to determine which of the player wins.
  arXiv  Detail & Related papers  (2020-02-04T19:28: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.