Computational Complexity of Non-Hermitian Quantum Systems

• URL: http://arxiv.org/abs/2506.03435v1
• Date: Tue, 03 Jun 2025 22:35:28 GMT
• Title: Computational Complexity of Non-Hermitian Quantum Systems
• Authors: Brian Barch, Daniel Lidar,
• Abstract summary: conditional time evolutions arise when a quantum system is monitored and one postselects on a measurement record.<n>We establish an approximate equivalence between post-selection and arbitrary non-Hermitian Hamiltonians.<n>Non-Hermitian physics neither guarantees a quantum advantage nor precludes efficient classical simulation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze the computational power of non-Hermitian quantum dynamics, i.e., conditional time evolutions that arise when a quantum system is monitored and one postselects on a particular measurement record. We establish an approximate equivalence between post-selection and arbitrary non-Hermitian Hamiltonians. Namely, first we establish hardness in the following sense: Let $U=e^{-iHt}$ be an NH gate on $n$ qubits whose smallest and largest singular values differ by at least $2^{-\text{poly}(n)}$. Together with any universal set of unitary gates, the ability to apply such a gate lets one efficiently emulate postselection. The resulting model decides every language in PostBQP; hence, under standard complexity conjectures, fully scalable NH quantum computers are unlikely to be engineered. Second, we establish upper bounds which show that conversely, any non-Hermitian evolution can be written as a unitary on a system-meter pair followed by postselecting the meter. This ``purification'' is compact -- it introduces only $O(\delta^{2})$ Trotter error per time step $\delta$ -- so any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently simulable. Thus, non-Hermitian physics neither guarantees a quantum advantage nor precludes efficient classical simulation: its complexity is controlled by the singular-value radius of the evolution operator and by the structure of its unitary purification.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Sample-Efficient Quantum State Tomography for Structured Quantum States in One Dimension [25.333797381352973]
  Many physical quantum states often exhibit certain low-dimensional structures that enable the development of efficient QST.<n>We show that the number of state copies to guarantee bounded recovery error of an MPO state with a constrained least-squares estimator depends on the probability distribution of the MPO.<n>We prove that only a number of state copies proportional to the number of independent parameters in the MPO is sufficient for a guaranteed recovery of any state represented by an MPO.
  arXiv  Detail & Related papers  (2024-10-03T15:26:26Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Discrete-coordinate crypto-Hermitian quantum system controlled by time-dependent Robin boundary conditions [0.0]
  unitary quantum mechanics formulated in non-Hermitian (or, more precisely, in hiddenly Hermitian) interaction-picture representation is illustrated via an elementary $N$ by $N$ matrix Hamiltonian $H(t)$ mimicking a 1D-box system with physics controlled by time-dependent boundary conditions. Our key message is that contrary to the conventional beliefs and in spite of the unitarity of the evolution of the system, neither its "Heisenbergian Hamiltonian" $Sigma(t)$ nor its "Schr"odingerian Hamiltonian" $G(
  arXiv  Detail & Related papers  (2024-01-19T13:28:42Z)
• Sachdev-Ye-Kitaev model on a noisy quantum computer [1.0377683220196874]
  We study the SYK model -- an important toy model for quantum gravity on IBM's superconducting qubit quantum computers. We compute return probability after time $t$ and out-of-time order correlators (OTOC) which is a standard observable of quantifying the chaotic nature of quantum systems.
  arXiv  Detail & Related papers  (2023-11-29T19:00:00Z)
• A Unifying Quantum Speed Limit For Time-Independent Hamiltonian Evolution [0.3314882635954752]
  We show that the Mandelstam-Tamm bound can be obtained by optimizing the Lee-Chau bound over a certain parameter. We find that if the dimension of the underlying Hilbert space is $lesssim 2000$, our unifying bound optimized over $p$ can be computed accurately in a few minutes.
  arXiv  Detail & Related papers  (2023-10-13T01:52:04Z)
• Exponentially improved efficient machine learning for quantum many-body states with provable guarantees [0.0]
  We provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications. Our results provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications.
  arXiv  Detail & Related papers  (2023-04-10T02:22:36Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans\"atze [13.651587339535961]
  We develop a framework for convolutional quantum circuits with SU$(d)$symmetry. We prove Harrow's statement on equivalence between $nameSU(d)$ and $S_n$ irrep bases.
  arXiv  Detail & Related papers  (2021-12-14T18:03:43Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Straddling-gates problem in multipartite quantum systems [20.428960719376164]
  We study a variant of quantum circuit complexity, the binding complexity. We show that any $m$partite Schmidt decomposable state has binding complexity linear in $m$, which hints its multi-separable property.
  arXiv  Detail & Related papers  (2021-10-13T16:28:12Z)
• 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)
• Hartree-Fock on a superconducting qubit quantum computer [30.152226344347064]
  Here, we perform a series of quantum simulations of chemistry the largest of which involved a dozen qubits, 78 two-qubit gates, and 114 one-qubit gates. We model the binding energy of $rm H_6$, $rm H_8$, $rm H_10$ and $rm H_12$ chains as well as the isomerization of diazene. We also demonstrate error-mitigation strategies based on $N$-representability which dramatically improve the effective fidelity of our experiments.
  arXiv  Detail & Related papers  (2020-04-08T18:00:06Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.