Fine-Grained Unambiguous Measurements

• URL: http://arxiv.org/abs/2510.07298v2
• Date: Tue, 04 Nov 2025 18:57:14 GMT
• Title: Fine-Grained Unambiguous Measurements
• Authors: Quentin Buzet, André Chailloux,
• Abstract summary: We introduce the notion of fine-grained unambiguous measurements.<n>We show that determining the maximal number of parities that a measurement can output can be formulated as a linear program.<n>We discuss the implications of these findings for the Quantum Decoding Problem.
• Score: 2.5782420501870296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Unambiguous measurements play an important role in quantum information, with applications ranging from quantum key distribution to quantum state reconstruction. Recently, such measurements have also been used in quantum algorithms based on Regev's reduction. The key problem for these algorithms is the S-$|LWE>$ problem in the lattice setting and the Quantum Decoding Problem in the code setting. A key idea for addressing this problem is to use unambiguous measurements to recover $k$ coordinates of a code (or lattice) element $x$ from a quantum state $|\psi_x\rangle$, which corresponds to a noisy word $x$ with errors in quantum superposition. However, a general theoretical framework to analyze this approach has been lacking. In this work, we introduce the notion of fine-grained unambiguous measurements. Given a family of states $\{\,|\psi_x\rangle\,\}_{x\in\{0,1\}^n}$, we ask whether there exist measurements that can return, with certainty, $k$ bits of information about $x$. We study this question in the setting of symmetric states, which naturally arises in the Quantum Decoding Problem. We show that determining the maximal number of parities that a measurement can output can be formulated as a linear program, and we use its dual formulation to derive several upper bounds. In particular, we establish necessary and sufficient conditions for the existence of fine-grained unambiguous measurements and prove impossibility results showing, in particular, that such measurements cannot improve upon the approach of arXiv:2310.20651. Finally, we discuss the implications of these findings for the Quantum Decoding Problem.

Related papers

• Shallow quantum circuit for generating O(1)-entangled approximate state designs [6.161617062225404]
  We find a new ensemble of quantum states that serve as an $epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence.<n>These resources can reach their theoretical lower bounds, $Omega(log (t/epsilon))$, which are also proven in this work.<n>A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states.
  arXiv  Detail & Related papers  (2025-07-23T18:56:19Z)
• Sample-optimal learning of quantum states using gentle measurements [2.867517731896504]
  We introduce here the class of $alpha-$locally-gentle measurements ($alpha-$LGM) on a finite dimensional quantum system.<n>We prove a strong quantum Data-Processing Inequality (qDPI) on this class using an improved gentleness between relation and quantum differential privacy.<n>We propose an $alpha-$LGM called quantum Label Switch that attains these bounds.
  arXiv  Detail & Related papers  (2025-05-30T13:34:11Z)
• 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)
• Purest Quantum State Identification [14.22473588576799]
  We introduce the purest quantum state identification, which can be used to improve the accuracy of quantum computation and communication.<n>For incoherent strategies, we derive the first adaptive algorithm achieving error probability $expleft(- Omegaleft(fracN H_1log(K) 2nfracright)$, fundamentally improving quantum property learning.
  arXiv  Detail & Related papers  (2025-02-20T07:42:16Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Configurable sublinear circuits for quantum state preparation [1.9279780052245203]
  We show a configuration that encodes an $N$-dimensional state by a quantum circuit with $O(sqrtN)$ width and depth and entangled information in ancillary qubits. We show a proof-of-principle on five quantum computers and compare the results.
  arXiv  Detail & Related papers  (2021-08-23T13:52:43Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum Algorithm for Quantum State Discrimination via Partial Negation and Weak Measurement [1.2691047660244335]
  A quantum algorithm using weak measurement and partial negation will be proposed to solve the quantum state discrimination problem. The proposed algorithm will be able to determine, with high probability of success, the state of the unknown qubit.
  arXiv  Detail & Related papers  (2021-02-23T21:18:19Z)
• Complexity of quantum state verification in the quantum linear systems problem [0.12891210250935145]
  We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A vec x = vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=Omega(kappa)$.
  arXiv  Detail & Related papers  (2020-07-30T19:20:49Z)
• Describing quantum metrology with erasure errors using weight distributions of classical codes [9.391375268580806]
  We consider using quantum probe states with a structure that corresponds to classical $[n,k,d]$ binary block codes of minimum distance. We obtain bounds on the ultimate precision that these probe states can give for estimating the unknown magnitude of a classical field.
  arXiv  Detail & Related papers  (2020-07-06T16:22:40Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.