Determining whether a quantum evolution can be efficiently simulated classically is central to understanding the boundary between classical and quantum computation. However, polynomial-time simulability is an asymptotic statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. In this work, we ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware. We analyze this question using three resource metrics, quantum sample, quantum time, and classical time complexity, for several widely studied classically simulable circuit families. Using representative hardware-level estimates, we identify regimes in which quantum simulation can be faster despite the existence of a polynomial-time classical algorithm, as well as regimes in which classical simulation remains more efficient. At the same time, the large quantum sampling cost needed to characterize unknown input states can make this polynomial-time classical simulation prohibitively expensive with current cloud-based hardware access prices. Ultimately, our work indicates that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.
S. Chang, Supanut Thanasilp, Zoe Holmes et al.· 0 citations
Multipartite entanglement admits phenomena such as the activation of genuine multipartite entanglement (GME) and the existence of inequivalent classes of entanglement, and existing bipartite entanglement measures have no unique generalization to this regime. In this work, we define the Rains, monsoon, hurricane, and squall entanglement as generalizations of the bipartite Rains relative entropy, and we establish various properties of these entanglement measures. We also prove that the Rains entanglement is monotone under selective quantum operations that completely preserve the positivity of the partial transpose. We establish single-letter upper bounds on the one-shot and asymptotic rates at which a fixed pure state can be distilled from an arbitrary state in both the standard and probabilistic approximate distillation scenarios. Among the entanglement measures we define, the tightest upper bound on the one-shot pure-state distillation rate is in terms of the Rains entanglement. However, the activation of GME (or, equivalently, the tensor instability of biseparability) makes it unclear if the one-shot bound in terms of the Rains entanglement can be extended to a single-letter asymptotic bound. Instead, we establish upper bounds on the asymptotic pure-state distillation rate in terms of the hurricane and squall entanglement. Upper bounds on the GHZ- and W-distillable entanglement follow as a consequence. Additionally, we define the multipartite max-Rains entanglement, write it as a semidefinite program, and derive a dual program for it. Finally, we analyze these measures for quantum pairwise independent networks, and we establish a conditional gradient (Frank-Wolfe) algorithm for computing the Rains entanglement.
Hailey S. Murray, Sagnik Bhattacharya, M. Cerezo et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
