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
- Daniel Fredriksen (ORCID: https://orcid.org/0009-0002-9123-7435)
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