A fixed Pauli-norm threshold for diagonal matrix powering

For every fixed Pauli coefficient-norm cap above one, distinguishing a single unnormalized basis diagonal of a polynomial matrix power at thresholds 9/32 and 7/32 is PromiseBQP-complete, even with explicitly listed dyadic coefficients and a positive definite contraction. Any estimate accurate to 1/32 decides the reduced instances. At cap one an efficient classical sampler is known. The fixed-error hardness also holds on an open nearest-neighbor chain of 16-dimensional sites with position-dependent interactions and a computational-basis product input. We extend polynomial-time fixed-error classical estimation near weight one, characterize the weighted coefficient mass of uniformly accurate scalar filters up to constants in the exponent, and evaluate this sampling guarantee on the rounded spin chains. On a real three-wire family, scoring a single returning path after summing two steps exactly has exponential variance, including after coefficient rounding. On a separate matched YES/NO pair with q work bits, the specified two-step row sampler gives exact single-score laws at total variation distance at most 2^(-q). A decoder receiving only independent scalar scores needs at least 2^q/3 trials for success 2/3 on both inputs, including with capped draws. A Clifford basis found by weighted vertex cover gives polynomial-time fixed-error estimation when the least weight beta_* whose deletion leaves commuting terms obeys beta_* <= 1/4 and m beta_* = O(log^2 L). On a growing two-local family, deleting the remainder changes the answer by at least 1/2-o(1). The deletion-weight cap alone still admits PromiseBQP-complete decisions.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24362437
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A fixed Pauli-norm threshold for diagonal matrix powering

Daniel Fredriksen
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

A fixed Pauli-norm threshold for diagonal matrix powering

Daniel Fredriksen
preprint en

Abstract

For every fixed Pauli coefficient-norm cap above one, distinguishing a single unnormalized basis diagonal of a polynomial matrix power at thresholds 9/32 and 7/32 is PromiseBQP-complete, even with explicitly listed dyadic coefficients and a positive definite contraction. Any estimate accurate to 1/32 decides the reduced instances. At cap one an efficient classical sampler is known. The fixed-error hardness also holds on an open nearest-neighbor chain of 16-dimensional sites with position-dependent interactions and a computational-basis product input. We extend polynomial-time fixed-error classical estimation near weight one, characterize the weighted coefficient mass of uniformly accurate scalar filters up to constants in the exponent, and evaluate this sampling guarantee on the rounded spin chains. On a real three-wire family, scoring a single returning path after summing two steps exactly has exponential variance, including after coefficient rounding. On a separate matched YES/NO pair with q work bits, the specified two-step row sampler gives exact single-score laws at total variation distance at most 2^(-q). A decoder receiving only independent scalar scores needs at least 2^q/3 trials for success 2/3 on both inputs, including with capped draws. A Clifford basis found by weighted vertex cover gives polynomial-time fixed-error estimation when the least weight beta_* whose deletion leaves commuting terms obeys beta_* <= 1/4 and m beta_* = O(log^2 L). On a growing two-local family, deleting the remainder changes the answer by at least 1/2-o(1). The deletion-weight cap alone still admits PromiseBQP-complete decisions.

Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon