PaperlayerView exact revision on arXiv

Source-linked AI summary

Verifiable Quantum Advantage via Optimized DQI Circuits

Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, Stephen P. Jordan

arXiv:2510.10967v1quant-ph

TL;DR

Verifiable quantum advantage seeks quantum solutions to optimization problems that can be checked classically, but existing proposals can require more gates than the theoretical lower bound. This paper applies DQI to OPI and develops optimized reversible Reed–Solomon decoding circuits. It reports optimal asymptotic gate scaling and estimates 5.72 million Toffoli gates for a classically intractable instance.

  • Problem

    Verifiable quantum advantage aims to solve classical search and optimization problems efficiently on quantum computers while allowing efficient classical checking.

    Source: §I · p. 2

  • Method

    The paper applies DQI to OPI, whose dual code is Reed–Solomon, and develops optimized reversible EEA-based decoder circuits.

    Source: §I · pp. 3–4

  • Results

    Approximately 5.72 million Toffoli gates and 1885 logical qubits are estimated for a classically intractable OPI instance with m=4095, n=70, and b=12.

    Source: §I · p. 4, §VI · p. 32

  • Takeaways & Limitations

    DQI for OPI is presented as a verifiable quantum-advantage candidate with eO(N) gates for O(2^N)-hard instances, matching the theoretical lower bound.

    Source: §I · p. 2, §VI · p. 32

Abstract

from arXiv · show

Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups by reducing certain optimization problems to reversible decoding tasks. We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose dual code is Reed-Solomon (RS). We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal asymptotic speedup: solving instances with classical hardness $O(2^N)$ requires only $\widetilde{O}(N)$ quantum gates, matching the theoretical lower bound. Realizing this speedup requires highly efficient reversible RS decoders. We introduce novel quantum circuits for the Extended Euclidean Algorithm, the decoder's bottleneck. Our techniques, including a new representation for implicit B\'ezout coefficient access, and optimized in-place architectures, reduce the leading-order space complexity to the theoretical minimum of $2nb$ qubits while significantly lowering gate counts. These improvements are broadly applicable, including to Shor's algorithm for the discrete logarithm. We analyze OPI over binary extension fields $GF(2^b)$, assess hardness against new classical attacks, and identify resilient instances. Our resource estimates show that classically intractable OPI instances (requiring $>10^{23}$ classical trials) can be solved with approximately 5.72 million Toffoli gates. This is substantially less than the count required for breaking RSA-2048, positioning DQI as a compelling candidate for practical, verifiable quantum advantage.

I. INTRODUCTION

The paper develops resource-efficient reversible Reed–Solomon decoding circuits to implement DQI for OPI. It argues that this combination achieves the optimal asymptotic gate scaling for verifiable quantum advantage and estimates concrete resources for OPI instances.

I. INTRODUCTION

  • DQI for OPI is presented as the first known verifiable quantum-advantage candidate using eO(N) gates for O(2^N)-hard instances, matching the Ω(N)-gate lower bound.The theorem states an NP-search or optimization problem with best-known classical runtime 2^N solvable by a circuit of eO(N) quantum gates.Source: §I · p. 2
  • Casting OPI as max-LINSAT yields a Vandermonde constraint matrix and a Reed–Solomon dual code, whose reversible decoding is central to DQI.The paper targets EEA-based syndrome-decoding circuits for that code.Source: §I · p. 3
  • The analysis shifts OPI to GF(2^b), reducing arithmetic costs and checking classical hardness against Prange’s algorithm and the extension-field Extended Prange variant.The paper reports that instances remain intractable against these attacks.Source: §I · pp. 3–4
  • Two EEA circuit regimes target minimal qubit overhead: in-place synchronized computation for explicit Bézout coefficients and Dialog trace storage for implicit access.The explicit circuit reaches leading-order space complexity 2nb qubits; Dialog targets low-gate, division-free EEA without its typically large qubit overhead.Source: §I · p. 4
  • For (m=4095, n=70, b=12), estimates require approximately 5.72 million Toffoli gates and 1885 logical qubits, with 800,000 physical qubits and 1 hour under stated assumptions.The physical estimate assumes a square nearest-neighbor grid, 0.1% gate error, 1-microsecond surface-code cycles, and 10-microsecond control reaction time.Source: §I · p. 4

II. METHODS FOR OPTIMIZED IMPLEMENTATION

  • The methods develop EEA compilation for explicit and implicit coefficient access, then integrate optimized EEA modules with Chien Search and Forney’s algorithm in a full reversible RS decoder.The approaches attain leading-order space complexity 2nb + O(log2(n)) and are discussed as useful beyond DQI, including elliptic-curve cryptography.Source: §II · p. 4, §I · p. 4

A. The DQI Quantum Circuit: An Improved Construction for Qubit Efficiency

  • The improved DQI circuit replaces the dense error representation with sparse error locations and sequentially generates, updates, then measurement-uncomputes each error symbol.This reuses a single b-qubit ancilla and reduces the syndrome-preparation ancilla cost to nb qubits; reversible decoding then uses nb + O(log2(n)) ancillas.Source: A. The DQI Quantum Circuit: An… · p. 5

Sparse Dicke State Preparation

  • Measurement-based uncomputation removes the error register during sequential syndrome computation, after which reversible decoding applies measurement-dependent phase fixups before the final inverse Fourier transform.Together, the construction avoids the original mb-qubit error-register overhead.Source: Sparse Dicke State Preparation · p. 7

B. Efficient Quantum Circuits for Extended Euclidean Algorithm

The paper develops reversible EEA circuits for Reed–Solomon decoding, distinguishing tasks that need stored Bézout coefficients from those that can use an implicit representation. Both approaches reduce qubit costs to 2nb + O(log n), while the explicit synchronized design also reduces dominant gate costs.

B. Efficient Quantum Circuits for Extended Euclidean Algorithm

  • The EEA maintains remainders and Bézout cofactors until the remainder reaches zero, leaving the previous remainder as the gcd and its cofactors as the Bézout coefficients.The remainder degree strictly decreases, guaranteeing termination.Source: B. Efficient Quantum Circuits for… · pp. 7–8
  • Both EEA constructions use 2nb + O(log n) qubits, matching the input-size lower bound, and have lower gate counts than prior state of the art.The two constructions support explicit and implicit Bézout-coefficient access.Source: B. Efficient Quantum Circuits for… · p. 8

1. Explicit versus Implicit Access to Bézout Coefficients

  • Implicit access stores compact representations of individual transition matrices instead of materializing the full Bézout coefficients, which can be applied sequentially when needed.For modular division, applying the transformations to [0, A(z)]^T yields A(z)B(z)^-1 mod P(z) without storing the inverse polynomial.Source: §1 · p. 9

2. Synchronized Reversible EEA for Explicit Bézout coefficients

  • The synchronized explicit-access circuit stores quotients in available shared-register padding, rigorously achieving 2nb + O(log n) space without a heuristic quotient-size bound.Earlier synchronized implementations bounded quotient storage to O(log N) qubits, causing fidelity loss for large quotients.Source: §2 · p. 10
  • The unified cycle architecture combines division and Bézout updates, performing n quantum-quantum multiplications and controlled additions instead of duplicating those operations across separate cycles.The synchronized EEA terminates within 6n iterations in the worst case, for a leading cost of 6n^2 quantum-quantum multiplications.Source: §2 · p. 10

3. Dialog Representation for Implicit Bézout coefficients

The paper represents implicit Bézout coefficients with a Dialog of reversible transformations and constructs it in place using a leading-order 2nb qubits. It then applies the EEA circuits to Reed-Solomon decoding and studies OPI over binary extension fields.

3. Dialog Representation for Implicit Bézout coefficients

  • The Dialog records small invertible transformations from the EEA, providing an implicit representation of Bézout coefficients that can be replayed on other vectors.For constant-time division-free algorithms, it records branch decisions; the described form stores 2n field elements.Source: §3 · pp. 10–12
  • For explicit Bézout access, in-register quotient storage gives the synchronized reversible EEA a deterministic leading-order space cost of 2nb qubits.The quotient is stored temporarily in padding within the shared register, eliminating the auxiliary quotient register and its heuristic size bound.Source: Figure 1 · p. 11
  • The Dialog’s linear representation supports modular division and multiplication without materializing an inverse, and permits Bézout-polynomial evaluation by composing evaluated transformations.For modular division, the transformation is applied to a scaled input vector; evaluation uses the transformation matrices evaluated at the chosen field point.Source: §3 · p. 11
  • The in-place Dialog construction uses a leading-order 2nb qubits by reclaiming polynomial-register space as the transformation record grows.The invariant len(poly) + len(dialog) = 2n permits recovery of the remainders directly and Bézout coefficients by replaying the partial Dialog.Source: §3 · pp. 12–13

C. Optimal Polynomial Intersection (OPI) over binary extension fields

  • Twisted Bent Target OPI uses Maiorana-McFarland bent-function structure to reduce constraint-encoding gate cost from roughly O(q) to O(log q).The paper focuses its resource analysis on this structured variant while maintaining the problem’s classical hardness.Source: C. Optimal Polynomial Intersection… · p. 13

D. Decoding Reed Solomon Codes using the Extended Euclidean Algorithm

  • The RS decoder solves the key equation with the EEA, then finds error locations by Chien search and error values with Forney’s algorithm.The key-equation solution supplies the error-locator and error-evaluator polynomials; decoding efficiency depends on whether their EEA access is explicit or implicit.Source: D. Decoding Reed Solomon Codes using… · pp. 13–14
  • In the studied binary-extension-field regime, explicit access has a lower dominant Toffoli cost than implicit access, whose Dialog playback requires 2mn quantum-quantum multiplications.The explicit model’s dominant cost is mn quantum-classical multiplications, which can use only Clifford gates over GF(2^b); the comparison may differ over prime fields.Source: D. Decoding Reed Solomon Codes using… · pp. 14–15

III. CLASSICAL ATTACKS ON OPI

The section analyzes Prange’s algorithm and extension-field variants as classical attacks on OPI, including strategies for allocating constraints and choosing target sets. The authors report that selected target sets yield approximate optima better than those available from known polynomial-time algorithms.

III. CLASSICAL ATTACKS ON OPI

  • Prange’s attack enforces n sampled constraints by solving a linear system, then repeats trials to seek a higher satisfied-constraint fraction.The disregarded m − n constraints contribute an expected r/q · (m − n) satisfied clauses per trial.Source: §III · p. 15

A. Optimizing Prange’s Algorithm

  • A row-echelon generator matrix and Gray-code iteration over allowed coordinate values are proposed to reduce per-attempt work in Prange’s algorithm.The Gray code updates only two of the first n coordinates per iteration; over F2b this can use two vectorized SIMD operations.Source: A. Optimizing Prange’s Algorithm · p. 15

B. Extended Prange’s Algorithm over Extension Fields

  • Extended Prange allocates a budget of nb base-field constraints across coordinates, trading constraints spent for affine-subspace overlap probabilities P[s].An allocation assigns s constraints to each coordinate, with the resulting satisfaction chance determined by P[s].Source: B. Extended Prange’s Algorithm over… · p. 16

1. Expectation-Optimal XP Allocation Strategies via Linear Programming

  • Over F4 with |F| = 2 and n/m = 1/2, XP has expected value 1, compared with 3/4 for Prange’s algorithm.The expectation-optimal allocation can be computed by a linear program using the overlap values P[s].Source: §1 · pp. 16–17

2. Probability-Optimal XP Allocation Strategies via a Knapsack Solver

  • For a threshold above XP’s optimal expected fraction, the allocation can instead maximize the probability of reaching that threshold; this optimization is non-convex.The authors use a dynamic-programming algorithm to obtain approximate solutions to the probability-optimization problem.Source: §2 · p. 17

3. Search for good target sets for OPI over binary extension fields

  • Choosing target sets with small affine-subspace overlaps is an open problem, and the authors identify quadratic bent-function varieties as effective for their approximate-optimization setting.Prior work cited in the passage used a high-rate regime for exact solutions; DQI’s approximate objective allows a lower rate here.Source: §3 · pp. 17–18
  • The authors report better approximate optima than any known polynomial-time algorithm, using bent functions from the Maiorana-McFarland family as a target-set choice.They favor a lower code rate because the space cost is dominated by n, while DQI seeks approximate rather than exact solutions.Source: §3 · p. 18

4. Upper bounds on affine intersections of Maiorana-McFarland target sets

The section establishes upper bounds on intersections of affine subspaces of dimension k ≤ d < 2k−1 with R_k and S_k, using inductive estimates that analyze the recursive affine subspaces, including mixed formulas and the case where the four subspaces are distinct.

Inductive challenge

  • Mixed recursive formulas defeat naive induction because R_k intersections can exceed half of |A| by twice the amount allowed for S_k intersections.The respective excess bounds are 2^(k−1) and 2^(k−2).Source: §4 · p. 20

Proof technique

  • Cancellation of quadratic terms in indicator functions reveals hidden affine structure in combinations of R_k and S_k intersections.Writing 1_Sk(a + x) as 1_Sk(a) + ω(a, x) + 1_Sk(x) makes cancellation of the quadratic terms possible.Source: §4 · p. 20

Proxy lemma

  • For two translates A_1 and A_2 of the same linear subspace W, the proxy lemma gives |A_1 ∩ R_k| + |A_2 ∩ S_k| = |B_1| + 2|B_2 ∩ S_k|, with |B_1| + |B_2| = |W|.Each proxy set B_1 and B_2 is either empty or affine.Source: §4 · p. 21

Two-term corollary

  • If every affine B satisfies |B ∩ S_(k−1)| ≤ 2^(dim B−1)+2^(k−3), then paired e-dimensional mixed intersections are at most 2^e+2^(k−2).The paired affine spaces must be translates of the same linear subspace.Source: §4 · pp. 21–22

Upper bounds

  • For k ≤ d < 2k−1, |A ∩ R_k| ≤ 2^(d−1)+2^(k−1), while |A ∩ S_k| ≤ 2^(d−1)+2^(k−2).The bounds apply to every d-dimensional affine subspace A of F_2^(2k).Source: §4 · pp. 20, 23

Upper bounds on affine intersections of Maiorana-McFarland target sets

  • When the four recursive affine subspaces are not all distinct, the proof uses R_(k−1) ⊔ S_(k−1) = F_2^(k−2) and the inductive hypothesis to derive the bounds.The resulting estimates are |A ∩ R_k| ≤ 2^(d−1) + 2^(k−1) and |A ∩ S_k| ≤ 2^(d−1) + 2^(k−2).Source: §4 · p. 23
  • The bounds are |A ∩ R_k| ≤ 2^(d−1) + 2^(k−1) and |A ∩ S_k| ≤ 2^(d−1) + 2^(k−2).The R_k bound is shown in both the non-distinct and distinct cases; the S_k bound is likewise established across the case analysis.Source: §4 · pp. 23–24
  • When the four recursive affine subspaces are distinct, they are translations of the same linear subspace, and two can be combined into a (d−1)-dimensional affine space.This structure enables the distinct-case intersection bounds, which use corollaries with e = d−2.Source: §4 · pp. 23–24

C. Asymptotic Classical Hardness of Twisted Bent Target OPI

The section defines Twisted Bent Target OPI (TBT-OPI) instances and establishes an exponential lower bound on the number of XP trials needed to solve them.

C. Asymptotic Classical Hardness of Twisted Bent Target OPI

IV. ASYMPTOTICALLY OPTIMAL QUANTUM SPEEDUP

The section presents alternative circuit implementations for near-term problem sizes and relates the asymptotic speedup theorem to the XP lower bound. These implementations need not optimize constant factors at smaller sizes.

IV. ASYMPTOTICALLY OPTIMAL QUANTUM SPEEDUP

  • Alternative implementations are used to establish the quantum-side result, which combines with the XP runtime lower bound to yield Theorem I.1.The section contrasts these implementations with the constant-factor optimizations for finite-size implementations in Section II.Source: §IV · p. 25

A. Asymptotically Optimal Implementation

Under stated conditions on field size and constraint encoding, DQI for OPI has near-linear gate complexity in m. The section analyzes the algorithm's stages and contrasts this regime with general OPI instances.

A. Asymptotically Optimal Implementation

B. Asymptotic Optimality

Theorem I.1 gives an NP-search/optimization problem with best-known classical runtime 2^N and a quantum circuit using eO(N) gates. This is the largest possible classical–quantum runtime separation under the stated circuit-simulation bound, though faster classical OPI algorithms may exist.

B. Asymptotic Optimality

  • 2^N classical runtime versus eO(N) quantum gates establishes an asymptotically optimal speedup for the stated NP-search/optimization problem.The result follows by combining Theorem IV.2 with the lower bounds in Theorem III.7.Source: B. Asymptotic Optimality · p. 26
  • Because an n-gate quantum circuit can be simulated classically in O(2^n) time, this speedup provides the largest possible classical–quantum runtime separation.The authors describe OPI as essentially contrived and no more quantum or natural than factoring or period-finding.Source: B. Asymptotic Optimality · p. 26
  • Known OPI attacks take exponential time in the number of evaluation points, but better classical algorithms may exist.The known algorithms do not exploit OPI’s low-degree algebraic structure and instead treat it as arbitrary max-LINSAT.Source: B. Asymptotic Optimality · p. 26
  • Whether further ideas could yield an asymptotically optimal speedup based on Shor’s algorithm remains an open question.The authors point to ideas along the lines of.Source: B. Asymptotic Optimality · p. 27
  • The analysis omits polylogarithmic factors, whose optimization may or may not improve practical performance at useful problem scales.The authors leave open whether removing these factors would yield a more practically usable speedup or merely add complexity.Source: B. Asymptotic Optimality · p. 27

V. RESOURCE ESTIMATES

The resource analysis compares reversible-decoder implementations and estimates logical and physical costs for classically intractable OPI instances. Its conclusion reports an asymptotically optimal DQI+OPI candidate, while noting open questions about the classical hardness analysis.

A. Logical Costs

  • Zalka’s EEA costs more gates but provides explicit Bézout coefficients for Clifford-only Chien-search evaluations, whereas Dialogs lower EEA cost but make evaluations more expensive.Both approaches use 2nb + O(log2(n)) qubits.Source: A. Logical Costs · p. 27
  • Several classically intractable OPI instances use two to three orders of magnitude fewer Toffoli gates than RSA-2048 factoring, but two to three times more logical qubits.The comparison reports RSA-2048 at approximately 6.5 × 10^9 Toffoli gates and 1399 logical qubits.Source: A. Logical Costs · p. 27

B. Physical Costs

  • For (m = 4095, n = 70, b = 12), the layout assigns 1920 logical qubits to cold storage and 120 to hot storage, totaling approximately 800,000 physical qubits.Hot patches use 968 physical qubits per logical qubit and cold storage uses 350.Source: B. Physical Costs · p. 28, Figure 5 · p. 31
  • The physical estimate is about 800,000 physical qubits and one hour, assuming a 1-microsecond surface-code cycle, 10-microsecond control reaction, nearest-neighbor grid, and 0.1% gate error rate.The layout combines hot surface-code patches and denser cold storage.Source: B. Physical Costs · p. 28

VI. CONCLUSION

  • The Dialog representation supports implicit Bézout-coefficient access, and in-place register sharing reduces decoder space complexity to the theoretical minimum of 2nb qubits.The techniques also substantially lower gate counts and are described as applicable to quantum algorithms relying on the EEA, particularly for Elliptic Curve Cryptography.Source: §VI · p. 32
  • >10^23 classical trials, 5.72 million Toffoli gates, and 1885 logical qubits characterize a reported OPI instance; physical estimates reach about 800,000 qubits and one hour.The estimates are reported for OPI over binary extension fields; the physical estimate uses a fault-tolerant architecture.Source: Table VI · p. 27, B. Physical Costs · p. 28, §VI · p. 32
  • The classical-hardness analysis remains open to refinement, including investigation of sophisticated algebraic attacks and formal average-case hardness guarantees.The authors report resilience against known attacks in the low-rate approximation regime.Source: §VI · p. 32

Appendix A: Optimizing the number of trials of Extended Prange

The appendix develops a dynamic program to approximate the Extended Prange trial optimization and describes sparse Dicke-state preparation as a space-efficient way to encode error locations.

Appendix A: Optimizing the number of trials of Extended Prange

  • The dynamic program compares candidate probability distributions using a fast rule that is usually within 5% of optimal and a slower convolution-based rule.The authors found no disagreement between the slower rule and brute force in their tests, though they note such cases theoretically exist; runtimes are O(mbBt) and O(mbBt^2), respectively.Source: Appendix A · p. 35

1. Upper Bound on the objective function

  • For the objective's specific P[s] function, allocating budget to s = k + 1 maximizes expected value and yields a greedy upper bound.The argument selects the allocation with the greatest gain per unit cost.Source: §1 · p. 36

Appendix B: Sparse Dicke State Preparation

  • When m is much larger than l = n/2, sparse encoding represents error locations with l log2 m qubits instead of m.The appendix also presents Combinatorial Number System preparation and two combination-unranking circuits, optimizing either asymptotic complexity or constant factors.Source: Appendix B · p. 37

1. The unranking strategy

Sparse Dicke-state preparation maps uniformly superposed combination ranks to their corresponding index combinations. The appendix gives both an asymptotically efficient divide-and-conquer unranking circuit and a lower-constant-factor iterative alternative.

1. The unranking strategy

  • The unranking strategy prepares a uniform superposition of ranks, then maps each rank to its corresponding combination with UUnrank.The Combinatorial Number System supplies the rank-to-combination bijection.Source: §1 · p. 37

2. Divide and Conquer Unranking for eO(m) Dicke State Preparation

  • The divide-and-conquer method splits the combination across two halves, uses binary splitting for hypergeometric prefix sums, and achieves eO(m) unranking complexity.Reversible binary splitting costs eO(k log m); the work per recursion level is eO(m), yielding total eO(m) complexity.Source: §2 · p. 38

3. Iterative Unranking for low constant factor Dicke State Preparation

  • The iterative unranking circuit uses 2kb + b qubits and O(mk + k^2b^2) Toffoli gates, trading the divide-and-conquer design for low constant factors.Its stated Toffoli costs include km for sparse QROMs and O((k log2 m)^2) for comparators.Source: §3 · p. 39

Appendix C: Improved arithmetic circuits for binary extension fields

The appendix optimizes binary-field arithmetic circuits and describes measurement-based uncomputation for multiplication. It also bounds the cycle cost of synchronized reversible polynomial EEA iterations.

1. Parity Control Toffoli PCTOF and Parity CNOT PCNOT

  • When PCTOF control sets are disjoint, their control parities can be computed in one cycle, while PCNOT can use one lattice-surgery cycle given enough ancillae.The optimized multiplication circuits start with CNOT stages followed by PCTOF gates; the table caption specifies counts for m = 10, 11, 12 over two gate libraries.Source: §1 · p. 39, Table VII · p. 39, §2 · p. 40

2. GF(2m) arithmetic circuits

  • The GF(2^m) multiplication optimization uses PCTOF gates, whose commuting degree-2 Boolean operations can be represented by vectors to identify redundant gates.The authors report a small optimization over and attribute its limited size to the optimizations already incorporated there.Source: §2 · p. 40

3. Measurement-based Uncomputation for GF2 Multiplication.

  • Measurement-based uncomputation corrects GF(2^m) multiplication using an X-basis target measurement and CZ gates, without needing the product to correct the phase.The cited CZ circuit can be implemented with depth floor(m/2 + 0.4993 log2(m) + 3.0191 log(m) - 10.9139) and at most m^2/4 + O(m log2(m)) Clifford gates.Source: §3 · p. 40

Appendix D: Bounding the number of iterations for Synchronized Reversible Polynomial EEA

  • The optimized synchronized PEEA costs Ti = 2di + si + di−1 + 2 cycles per iteration and T = 3Dk + Sk − dk + 2k cycles over k iterations.For Full PEEA on coprime inputs of unequal degrees, Dk = Sk = n.Source: Appendix D · p. 42

1. Worst-Case Analysis: Full PEEA (GCD)

The appendix bounds synchronized PEEA cycle counts for full and half decoding runs and supplies deferred bounds and identities for affine intersections with Maiorana-McFarland target sets.

1. Worst-Case Analysis: Full PEEA (GCD)

  • The maximum cycle count for optimized synchronized Full PEEA is 6n − 1, attained by the generalized Fibonacci sequence with di = si = 1.The bound concerns worst-case coprime inputs with degrees (n, n − 1).Source: §1 · p. 42

2. Worst-Case Analysis: Half PEEA (Reed-Solomon Decoding)

  • The maximum cycle count for optimized synchronized Half-PEEA is 6⌊n/2⌋ + 5.The stated slow-convergence scenario has di = si = 1 at each iteration.Source: §2 · p. 43

Appendix E: Deferred proofs of upper bounds on affine intersections of Maiorana-McFarland target sets

  • For dim A = 2k − 1, the appendix proves |A ∩ Rk| ≤ 2^(2k−2) + 2^(k−1), and gives |Rk| = 2^(2k−1) + 2^(k−1) and |Sk| = 2^(2k−1) − 2^(k−1).It also reduces a four-term affine-intersection sum to |B1| + 2|B2 ∩ Sk| for suitable sets B1 and B2.Source: Appendix E · pp. 43, 44, 45, 47

1. Reed Solomon Decoding using Synchronized EEA for Explicit Bézout coefficients

The section presents optimized reversible EEA-based Reed-Solomon decoding in explicit and Dialog-based forms, with register sharing supporting downstream decoder operations.

1. Reed Solomon Decoding using Synchronized EEA for Explicit Bézout coefficients

  • Fig. 10 uses the optimized EEA as a subroutine for Chien Search and Forney’s algorithm, with shared in-place registers for σ(z) and Ω(z).Source: §1 · p. 48, Figure 10 · p. 50

2. Reed Solomon Decoding using Dialog based EEA for Implicit Bézout Coefficients

1. Reed Solomon Decoding using Synchronized EEA for Explicit Bézout coefficients

  • Fig. 9 presents an optimized implementation of Zalka’s synchronized reversible EEA with explicit Bézout-coefficient access.Source: §1 · p. 48, Figure 9 · p. 49

Related papers

Loading 2510.10967v1…