Computational aspects of the trace norm contraction coefficient

• URL: http://arxiv.org/abs/2507.16737v1
• Date: Tue, 22 Jul 2025 16:22:07 GMT
• Title: Computational aspects of the trace norm contraction coefficient
• Authors: Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran,
• Abstract summary: We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard.<n>We also establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.
• Score: 4.916646834691489
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly by solved efficiently. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

Related papers

• A Unified Approach to Quantum Contraction and Correlation Coefficients [10.128808054306187]
  We introduce a family of non-commutative $L2(p)$ spaces induced by operator monotone functions.<n>We identify families of quantum maximal correlation coefficients and the quantum $chi2$-divergences.
  arXiv  Detail & Related papers  (2025-05-21T08:58:45Z)
• Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing [5.211732144306638]
  We study contraction coefficient for hockey-stick divergence under privacy constraints.<n>We also show how private quantum channels provide fairness and Holevo information stability in quantum learning settings.
  arXiv  Detail & Related papers  (2024-06-26T18:00:03Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Quantum Soft Covering and Decoupling with Relative Entropy Criterion [11.987004396261241]
  We prove covering lemmas by deriving one-shot bounds on the rates in terms of smooth min-entropies and smooth max-divergences. We present a one-shot quantum decoupling theorem with relative entropy criterion.
  arXiv  Detail & Related papers  (2024-02-16T22:31:38Z)
• Quantum complexity of the Kronecker coefficients [2.2983894078587963]
  We show that a given Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier. This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting problems.
  arXiv  Detail & Related papers  (2023-02-22T15:43:26Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• 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)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
  arXiv  Detail & Related papers  (2021-09-23T07:46:20Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

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.