Quantum Random Access Codes for Boolean Functions

• URL: http://arxiv.org/abs/2011.06535v4
• Date: Thu, 4 Mar 2021 09:19:50 GMT
• Title: Quantum Random Access Codes for Boolean Functions
• Authors: Jo\~ao F. Doriguello, Ashley Montanaro
• Abstract summary: We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding. The success probability of our protocols is characterized by the emphnoise stability of the Boolean function $f$.
• Score: 0.05076419064097732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An $n\overset{p}{\mapsto}m$ random access code (RAC) is an encoding of $n$ bits into $m$ bits such that any initial bit can be recovered with probability at least $p$, while in a quantum RAC (QRAC), the $n$ bits are encoded into $m$ qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function $f$ on any subset of fixed size of the initial bits, which we call $f$-random access codes. We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ($f$-EARAC) and Popescu-Rohrlich boxes ($f$-PRRAC). The success probability of our protocols is characterized by the \emph{noise stability} of the Boolean function $f$. Moreover, we give an \emph{upper bound} on the success probability of any $f$-QRAC with shared randomness that matches its success probability up to a multiplicative constant (and $f$-RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.

Related papers

• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Biased Random Access Codes [0.0]
  A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver. We present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies.
  arXiv  Detail & Related papers  (2023-02-16T18:53:25Z)
• Generating $k$ EPR-pairs from an $n$-party resource state [5.617510227362658]
  We show that LOCC protocols can create EPR-pairs between any $k$ disjoint pairs of parties. We also prove some lower bounds, for example showing that if $k=n/2$ then the parties must have at least $Omega(loglog n)$ qubits each.
  arXiv  Detail & Related papers  (2022-11-11T22:18:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Code-routing: a new attack on position verification [0.0]
  A popular verification scheme known as $f$-routing involves requiring the prover to redirect a quantum system. We give a new cheating strategy in which the quantum system is encoded into a secret-sharing scheme. This strategy completes the $f$-routing task using $O(SP_p(f))$ EPR pairs.
  arXiv  Detail & Related papers  (2022-02-16T01:04:31Z)
• The geometry of Bloch space in the context of quantum random access codes [0.0]
  We study the communication protocol known as a Quantum Random Access Code (QRAC) We prove that for any $(n,m,p)$-QRAC with shared randomness the parameter $p$ is upper bounded by $ tfrac12+tfrac12sqrttfrac2m-1n$.
  arXiv  Detail & Related papers  (2021-06-01T00:15:33Z)
• Random access codes via quantum contextual redundancy [0.0]
  We propose a protocol to encode classical bits in the measurement statistics of many-body Pauli observables. We exploit by encoding the data into a set of convenient context eigenstates. This allows to randomly access the encoded data with few resources.
  arXiv  Detail & Related papers  (2021-03-01T18:50:46Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
  A client remotely prepares a quantum state using a classical channel. Privacy loss incurred by employing $RSP_CC$ as a sub-module is unclear. We show that a specific $RSP_CC$ protocol can replace the quantum channel at least in some contexts.
  arXiv  Detail & Related papers  (2020-07-03T13:15:13Z)
• Capacity of Quantum Private Information Retrieval with Colluding Servers [71.78056556634196]
  Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from non-communicating servers. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol.
  arXiv  Detail & Related papers  (2020-01-13T18:12:20Z)

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.