The complexity of perfect quantum state classification

• URL: http://arxiv.org/abs/2510.20789v1
• Date: Thu, 23 Oct 2025 17:53:53 GMT
• Title: The complexity of perfect quantum state classification
• Authors: Nathaniel Johnston, Benjamin Lovitz, Vincent Russo, Jamie Sikora,
• Abstract summary: We introduce the notion of $k$-learnability, which captures the ability to identify the correct state using at most $k$ guesses, with zero error.<n>We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of $k$-learnability, which captures the ability to identify the correct state using at most $k$ guesses, with zero error. We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming. When there are $n$ states, we present polynomial-time (in $n$) algorithms for determining $k$-learnability for two cases: when $k$ is a fixed constant or the dimension of the states is a fixed constant. When both $k$ and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical $k$-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.

Related papers

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Optimal quantum state tomography with local informationally complete measurements [25.33379738135298]
  We study whether a general MPS/MPDO state can be recovered with bounded errors using only a number of state copies in the number of qubits. We provide a positive answer for a variety of common many-body quantum states, including typical short-range entangled states, random MPS/MPDO states, and thermal states of one-dimensional Hamiltonians.
  arXiv  Detail & Related papers  (2024-08-13T17:58:02Z)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  We present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. We give now-possible algorithms for the quantum change point identification problem which asks, given a sequence of quantum states, determine the time steps when the quantum states changed.
  arXiv  Detail & Related papers  (2023-12-07T03:42:40Z)
• State Classification via a Random-Walk-Based Quantum Neural Network [0.0]
  We introduce the quantum neural network (QSNN), and show its capability to accomplish the binary discrimination of quantum states. Other than binary discrimination, the QSNN is also applied to classify an unknown set of states into two types: entangled ones and separable ones. Our results suggest that the QSNN has the great potential to process unknown quantum states in quantum information.
  arXiv  Detail & Related papers  (2023-04-12T07:39:23Z)
• Multipartite entanglement and quantum error identification in $D$-dimensional cluster states [0.0]
  We show how to create $m$-uniform states using local gates or interactions. We show how to achieve larger $m$ values using quasi-$D$ dimensional cluster states. This opens the possibility to use cluster states to benchmark errors on quantum computers.
  arXiv  Detail & Related papers  (2023-03-27T18:00:02Z)
• Experimental demonstration of optimal unambiguous two-out-of-four quantum state elimination [52.77024349608834]
  A core principle of quantum theory is that non-orthogonal quantum states cannot be perfectly distinguished with single-shot measurements. Here we implement a quantum state elimination measurement which unambiguously rules out two of four pure, non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2022-06-30T18:00:01Z)
• 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)
• Stochastic approximate state conversion for entanglement and general quantum resource theories [41.94295877935867]
  An important problem in any quantum resource theory is to determine how quantum states can be converted into each other. Very few results have been presented on the intermediate regime between probabilistic and approximate transformations. We show that these bounds imply an upper bound on the rates for various classes of states under probabilistic transformations. We also show that the deterministic version of the single copy bounds can be applied for drawing limitations on the manipulation of quantum channels.
  arXiv  Detail & Related papers  (2021-11-24T17:29:43Z)
• Free versus Bound Entanglement: Machine learning tackling a NP-hard problem [0.06091702876917279]
  Entanglement detection in high dimensional systems is a NP-hard problem since it is lacking an efficient way. We find a family of magically symmetric states of bipartite qutrits for which we find $82%$ to be free entangled, $2%$ to be certainly separable and as much as $10%$ to be bound entangled.
  arXiv  Detail & Related papers  (2021-06-07T21:38:39Z)
• 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)
• 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.