Getting almost all the bits from a quantum random access code

• URL: http://arxiv.org/abs/2506.01903v1
• Date: Mon, 02 Jun 2025 17:24:30 GMT
• Title: Getting almost all the bits from a quantum random access code
• Authors: Han-Hsuan Lin, Ronald de Wolf,
• Abstract summary: A quantum random access code (QRAC) encodes $n$-bit strings $x$ into $m$-qubit quantum states.<n>For every QRAC there exists a measurement that recovers the full $n$-bit string $x$ up to small Hamming distance.
• Score: 2.0487816291664784
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A quantum random access code (QRAC) is a map $x\mapsto\rho_x$ that encodes $n$-bit strings $x$ into $m$-qubit quantum states $\rho_x$, in a way that allows us to recover any one bit of $x$ with success probability $\geq p$. The measurement on $\rho_x$ that is used to recover, say, $x_1$ may destroy all the information about the other bits; this is in fact what happens in the well-known QRAC that encodes $n=2$ bits into $m=1$ qubits. Does this generalize to large $n$, i.e., could there exist QRACs that are so "obfuscated" that one cannot get much more than one bit out of them? Here we show that this is not the case: for every QRAC there exists a measurement that (with high probability) recovers the full $n$-bit string $x$ up to small Hamming distance, even for the worst-case $x$.

Related papers

• Are controlled unitaries helpful? [3.084918555654188]
  We show that having access to $cU$ does not help for a large class of quantum problems.<n>We show how to decontrol'' a quantum circuit into one which uses only $U$ and $Udagger$ and outputs $|psi(varphi U)rangle$.
  arXiv  Detail & Related papers  (2025-07-31T18:00:01Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• Compression for Qubit Clocks [55.38708484314286]
  We propose a compression protocol for $n$ identically prepared states of qubit clocks. The protocol faithfully encodes the states into $(1/2)log n$ qubits and $(1/2)log n$ classical bits.
  arXiv  Detail & Related papers  (2022-09-14T09:45:53Z)
• Quantum Error Detection Without Using Ancilla Qubits [0.0]
  We describe and experimentally demonstrate an error detection scheme that does not employ ancilla qubits or mid-circuit measurements. This is achieved by expanding the Hilbert space where a single logical qubit is encoded using several physical qubits.
  arXiv  Detail & Related papers  (2022-04-23T17:51:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• 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)
• Tamper Detection against Unitary Operators [0.0]
  We extend the scope of the theory of tamper detection codes against an adversary with quantum capabilities. A quantum codeword $vert psi_m rangle$ can be adversarially tampered via a unitary $U$ from some known tampering unitary family. We show that quantum tamper detection codes exist for any family of unitary operators.
  arXiv  Detail & Related papers  (2021-05-10T16:26:41Z)
• 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 Random Access Codes for Boolean Functions [0.05076419064097732]
  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$.
  arXiv  Detail & Related papers  (2020-11-12T17:48:37Z)
• 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)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.