Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes

• URL: http://arxiv.org/abs/2606.04843v1
• Date: Wed, 03 Jun 2026 13:12:15 GMT
• Title: Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes
• Abstract summary: Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems.<n>We extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry.<n>We find solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample.
• Score: 39.146761527401424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decoded Quantum Interferometry (DQI) uses coherent decoding and a quantum Fourier transform to find high-quality solutions of structured optimisation problems. Existing analyses are closely tied to Hamming space, which underlies the optimisation objective, Dicke state preparation and the decoding step of the algorithm. Here we extend the core DQI mechanism beyond Hamming space to finite geometries with translation symmetry, where points are grouped into shells by their distance from a basepoint. Mathematically, these geometries are translation association schemes. In this setting the algorithm can be analysed by tracking one amplitude per shell, and biasing the prepared state towards high-quality solutions becomes a finite tridiagonal eigenvalue problem. As a non-Hamming example, we develop an efficient DQI protocol for finding an m x n finite-field matrix with smallest rank difference to a target matrix. Initial states are uniform superpositions over fixed-rank matrices, and Gabidulin codes provide candidates for efficient low-rank decoding up to a cutoff l. For this objective, this finds solutions with an effective-rank proxy near min(m,n)-l, and the corresponding expected score can be converted into a constant-probability bound on the residual rank of a sample. For Gabidulin nearest-codeword instances, a covering-radius obstruction shows that this bound does not imply an additive guarantee for the true optimum, and we do not claim a quantum advantage for the rank-metric construction. The results instead identify the geometric and coding ingredients for DQI beyond Hamming space.

Related papers

• Improved Measurement Cost Scaling in the Nonorthogonal Quantum Eigensolver [1.6328866317851187]
  We study a bottleneck for the nonorthogonal quantum eigensolver (NOQE)<n>We show that, after overlap thresholding, the eigenvalue sensitivity is controlled by the condition number of the retained overlap matrix.<n>Experiments on hydrogen chains and rings suggest that, in practice, the measurement cost of structured NOQE instances can grow even more slowly than this linear bound.
  arXiv  Detail & Related papers  (2026-08-13T05:05:55Z)
• Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation [6.1401581501410085]
  The algorithm is a hybrid quantum-classical framework for optimization on near-term quantum devices.<n>It encodes low-energy quantum samples into an Ising matrix and compresses it.
  arXiv  Detail & Related papers  (2026-06-05T19:47:28Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness [8.113729514518495]
  The Euclidean Distance Matrix Completion problem arises in a broad range of applications, including sensor network localization, molecular robustness, and manifold learning.<n>In this paper, we propose a low-rank matrix completion task over the space of positive semi-definite Gram matrices.<n>The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through nonnegativity and the triangle inequality.
  arXiv  Detail & Related papers  (2025-07-31T18:40:42Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  We propose the variational quantum singular value decomposition based on encoding the elements of the considered $Ntimes N$ matrix into the state of a quantum system of appropriate dimension.<n> Controlled measurement is involved to avoid small success in ancilla measurement.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  Two algorithms are proposed to solve the Euclidean Distance Geometry problem. First algorithm converges linearly to the true solution. Second algorithm demonstrates strong numerical performance on both synthetic and real data.
  arXiv  Detail & Related papers  (2024-10-08T21:19:22Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

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.