CS Paper Radar

How wide must an eavesdropper be? Leakage of a toric-code logical bit to a strip and the Nishimori point

Konstantinos Karagiannis

cs.CR quant-phcond-mat.stat-mech ·submitted 2026-11-09 19:57 UTC · v1
theory

Abstract

Fault-tolerant quantum computers hand pieces of each logical qubit to separate decoder modules and shared readout lines. How much does a piece reveal? We prove that for any region and any Pauli noise, including correlated noise, an observer's optimal advantage in learning a logical bit is exactly 1 - 2 P_fail, where P_fail is the failure probability of maximum-likelihood decoding confined to that region. Two lessons follow. Geometry, not noise, provides the protection: a region that misses a single column of the code learns exactly nothing at any noise level, while a region that spans the code is protected by noise only at impractical distances (d > 350 for one row at a 10^-3 flip rate). And width is a poor guide to risk: under i.i.d. noise a two-row strip learns exactly as little as one row, yet below threshold an eavesdropper needs a width growing only as ln d. Through the identity, the strip's operational threshold is the Nishimori point of the random-bond Ising model, and a Walsh-Hadamard transfer matrix up to width 16 locates it to within a few thousandths. On two IBM Heron processors (d = 3, 5), an emulated strip adversary shows the predicted jump at width three, and non-uniform qubit errors let a trained attacker profit from the second row that uniform noise makes useless. We turn these results into design rules for partitioned decoding and multiplexed readout. Code and data are included.

Comment
19 pages, 4 figures, 11 tables. Code, data, IBM Quantum shot records, transpiled circuits and calibration snapshots in ancillary files. Prepared with AI assistance; see "Use of AI tools"

Closest papers

Nearest neighbours by meaning across the whole index.

Learnt Attacks on Quantum Key Distribution under Channel Noise and Device Drift

cs.CR quant-phcs.ITcs.LG ·2026-10-01 ·Marcel Mordarski, Benjamin Gras, Abdelrahman Shehata, Daniel Budina, Roberto Bondesan
top venuetheory similarity 0.64
Abstract · Presented as submission 202 at QCrypt 2026 qcrypt.net/2026/technical/accepted-papers/. A parallel work exploring the machine-learning aspect…

Quantum key distribution (QKD) links are provisioned from security analyses of stationary channels, whereas the devices that determine the channel drift between recalibrations. Whether an eavesdropper who cannot alter the channel's own noise gains by following that drift has not been quantified. Adaptive eavesdropping is posed here as a constrained Markov decision process in which the attacker selects one circuit per round while the noise level follows an Ornstein--Uhlenbeck process and the abort condition is a budget over each block of rounds. The value of adaptation is bounded by the best fixed circuit and a dynamic-programming upper bound. The actions are learnt attacks. Whereas Decker et al. trained a parametrised circuit on a fixed gate template against a fixed channel, here the gate structure and rotation angles are searched jointly. This yields circuits compact enough to form a discrete action set, extending the construction to noise models lacking a known template, including the amplitude damping channel. On device-independent E91 under bilateral depolarising noise, a reinforcement-learning attacker raises her Holevo information from $0.135$ for the best fixed circuit to $0.348$ at zero detection, $98\%$ of the upper bound. On BB84 under a drifting bit-flip channel, she exceeds a conservative noise-indexed rule by $0.024$ in fidelity, reaching $99\%$ of the upper bound. Under stationary noise, the attacker's gain from basis asymmetry changes sign between an averaged and a per-basis error-rate constraint. The search, started from random gate sequences, recovers the analytical cloners and the collective-attack key rate, and meets the lower bound of the Winick--Lütkenhaus--Coles objective from above.

0.69

The Sample Complexity of Quantum Entanglement Allocation

cs.LG quant-ph ·2026-09-09 ·Nathan Roll
similarity 0.63
Abstract · 61 pages, 15 figures. Includes code and recorded data as ancillary files

How many past requests are needed to decide which qubits should share entanglement? We show that the answer depends on the allocation choices created by the queries: a larger memory can require no more data. The memory stores a classical bit and answers requests through a fixed detector that preserves coherence within each measured sector. For independent commuting $X$- and $Z$-type Pauli queries, we characterize the full attainable prediction-contrast region and construct encodings that preserve the bit at every nonzero vertex. With sharp reports, a $d$-qubit path and groups of at most $k$ qubits have minimax excess error after $m$ requests proportional to $k^{-1}\min\{1,\sqrt{d\log(k+1)/m}\}$, uniformly for $2\leq k<d$. Connected biclique regions can grow without increasing sample demand when depth, region count and connections per region stay bounded. Preparation noise introduces a separate calibration requirement. We derive an exact tradeoff with extra fresh detector calls and transfer the learning law to structured transaction co-location. Population-risk experiments test the statistical predictions. We also compare encodings on a native 15-qubit device and learned partitions on public purchase baskets. The full chain wins on the device; frequency grouping outperforms basket search in the largest-capacity retail setting.

0.30

Covering the Pauli Observables: Sampling Thresholds and the Design Effect of a Measurement Setting

cs.IT quant-pheess.SP ·2026-11-18 ·Kausthubh Chandramouli, Noah Siekierski, Bojko N. Bakalov, Dror Baron
similarity 0.63
Abstract · 30 pages, 5 figures, 3 tables

Quantum state tomography and shadow-based estimation rely on measuring Pauli observables. An experiment does not measure them one at a time: it chooses a measurement setting that assigns one of the bases X, Y or Z to each qubit, and a single run in that setting yields estimates of every Pauli observable compatible with it. We say that the setting covers those observables. We determine how many random settings cover a prescribed fraction of all Pauli observables. As the number of settings grows exponentially with the number of qubits, the covered fraction has a sharp threshold at a growth rate of $3^{3/4}$ per qubit, set by the rate-distortion function of covering at zero distortion. We give an explicit expression for the number of settings needed to reach a target fraction, accurate up to a remainder that reduces to a small oscillation for many qubits, and show that random sampling is asymptotically optimal up to a factor of less than 1.69. Coverage does not determine what a setting contributes to an estimator. Observables covered by one setting are estimated from the same outcomes, so their estimates are correlated. We quantify this correlation through the design effect of a setting, which equals the squared Pauli expectation that the setting captures and depends on the target state. We derive its mean over settings in closed form for every state and show that it can be estimated without bias from the measurement data. In simulations on six qubits, measuring settings needs 7.6 to 38 times fewer circuit runs than measuring the same number of observables independently. At high coverage, fitting the outcome histograms instead of averaged estimates roughly halves the reconstruction error, mainly because the fit counts how many settings cover each observable. The correlation itself costs such a fit about a factor of two, and a larger design effect signals more to gain from modeling it.

0.49

Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

cs.IT quant-ph ·2026-09-05 ·Avijit Mandal, Christophe Piveteau, Joseph M. Renes, Henry D. Pfister
highly cited similarity 0.62
Abstract

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=Θ(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

0.41

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
highly cited similarity 0.62
Abstract

We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.44

Certified decoding of quantum LDPC codes

cs.IT quant-ph ·2026-08-26 ·Ragavi Krishnamoorthy, Florian Gerhardt, Johannes Knaute, Thomas Klir, Stefan Raimund Maschek +6 more
similarity 0.61
Abstract

Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.

0.29

No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders

cs.DS quant-ph ·2026-11-09 ·Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Guneykan Ozgul +3 more
theory similarity 0.61
Abstract

Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random $D$-regular $k$-sparse instances with $k\ge3$, for which local decoders such as belief propagation with quantum messages (BPQM) are commonly used. Such decoders estimate a typical codeword symbol using only the qudits within logarithmic distance of it. Our main insight is that the thresholds of the decoding problem induced by DQI correspond to phase transitions of the Gibbs measure that are well studied in statistical physics: tree reconstruction for local decoders and, for Max-$k$-XORSAT, condensation for the optimal decoder. This insight allows us to prove two main results. First, we prove an information-theoretic obstruction: no local decoder can recover the codeword with high probability above the tree reconstruction threshold. Conversely, we show that a decoder based on BPQM reaches this threshold. Since the cavity method predicts that local Markov chains equilibrate rapidly up to the same threshold, we expect DQI with local decoders to give no exponential speedup for sampling and no advantage in approximate optimization with amplitude functions that depend only on the number of violated constraints. Second, we consider the optimal decoder (the pretty-good measurement, for which no efficient implementation is known) and show that it succeeds exactly below the condensation threshold. The condensation threshold thus provides a tight upper bound on the performance of DQI with these amplitude functions, providing a strict refinement of the limit that Jordan et al.\ derived from the Holevo bound. Our results point to efficient nonlocal decoders that succeed between the two thresholds as the only viable path to a quantum advantage with DQI on these instances.

0.36

Quantum Leakage Resilience of Shamir Secret Sharing

cs.CR quant-ph ·2026-09-29 ·Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
similarity 0.61
Abstract · 38 pages, 2 tables

We initiate the study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields. A well-studied leakage model for Shamir's secret sharing classically is single-bit local leakage from each share. We consider its quantum analogue where, for each party, a local leakage channel takes as input the party's share and outputs a leaked qubit. Without preshared entanglement, we show that the distinguishing advantage is $2^{-Ω(n)}$ when the threshold rate $t/n=τ$ exceeds $τ_\star\approx0.73339$ by a fixed positive margin. More generally, we allow disjoint entangled blocks of any fixed maximum size where there is no entanglement between different blocks or with the adversary, and each block emits at most a fixed number of qubits. Security holds when the threshold rate is high enough (sufficiently close to one). We then allow a specified set of devices to share entanglement with the adversary. We show that security holds even when a linear number of devices ($αn$ for small $α>0$) share entanglement with each other and with the adversary for a large enough threshold rate. As a complementary negative result, we also show that even classical single-bit leakage makes Shamir scheme insecure if we allow arbitrarily large entanglement between the leakage devices. A GHZ state shared by exactly $t$ leakage devices makes even classical one-bit leakage insecure, without any entanglement with the adversary. In this attack, each participating device emits only one classical bit, and their joint parity distinguishes any chosen pair of secrets with a constant advantage. Thus, for fixed threshold rates above $τ_\star$, the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in $n$ up to constant factors, although the optimal support fraction remains open.

0.61