Variational quantum algorithms (VQAs) optimize the parameters θ of a parametrized quantum circuit V(θ) to minimize a cost function C. While VQAs may enable practical applications of noisy quantum computers, they are nevertheless heuristic methods with unproven scaling. Here, we rigorously prove two results, assuming V(θ) is an alternating layered ansatz composed of blocks forming local 2-designs. Our first result states that defining C in terms of global observables leads to exponentially vanishing gradients (i.e., barren plateaus) even when V(θ) is shallow. Hence, several VQAs in the literature must revise their proposed costs. On the other hand, our second result states that defining C with local observables leads to at worst a polynomially vanishing gradient, so long as the depth of V(θ) is $${\mathcal{O}}(\mathrm{log}\,n)$$O ( log n ) . Our results establish a connection between locality and trainability. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.

Variational Quantum Algorithms (VQAs) may be a path to quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) computers. A natural question is whether noise on NISQ devices places fundamental limitations on VQA performance. We rigorously prove a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau (i.e., vanishing gradient). Specifically, for the local Pauli noise considered, we prove that the gradient vanishes exponentially in the number of qubitsnif the depth of the ansatz grows linearly withn. These noise-induced barren plateaus (NIBPs) are conceptually different from noise-free barren plateaus, which are linked to random parameter initialization. Our result is formulated for a generic ansatz that includes as special cases the Quantum Alternating Operator Ansatz and the Unitary Coupled Cluster Ansatz, among others. For the former, our numerical heuristics demonstrate the NIBP phenomenon for a realistic hardware noise model.

We study the Hamiltonian identifiability of a many-body spin-$1/2$ system assisted by the measurement on a single quantum probe based on the eigensystem realization algorithm approach employed in Zhang and Sarovar, Phys. Rev. Lett. 113, 080401 (2014). We demonstrate a potential application of Gröbner basis to the identifiability test of the Hamiltonian, and provide the necessary experimental resources, such as the lower bound in the number of the required sampling points, the upper bound in total required evolution time, and thus the total measurement time. Focusing on the examples of the identifiability in the spin-chain model with nearest-neighbor interaction, we classify the spin-chain Hamiltonian based on its identifiability, and provide the control protocols to engineer the nonidentifiable Hamiltonian to be an identifiable Hamiltonian.

In open quantum systems, a clear distinction between work and heat is often challenging, and extending the quantum Jarzynski equality to systems evolving under general quantum channels beyond unitality remains an open problem in quantum thermodynamics. In this Letter, we introduce well-defined notions of guessed quantum heat and guessed quantum work, by exploiting the one-time measurement scheme, which only requires an initial energy measurement on the system alone. We derive a modified quantum Jarzynski equality and the principle of maximum work with respect to the guessed quantum work, which requires the knowledge of the system only. We further show the significance of guessed quantum heat and work by linking them to the problem of quantum hypothesis testing.

The quantum ergotropy quantifies the maximal amount of work that can be extracted from a quantum state without changing its entropy. Given that the ergotropy can be expressed as the difference of quantum and classical relative entropies of the quantum state with respect to the thermal state, we define the classical ergotropy, which quantifies how much work can be extracted from distributions that are inhomogeneous on the energy surfaces. A unified approach to treat both quantum as well as classical scenarios is provided by geometric quantum mechanics, for which we define the geometric relative entropy. The analysis is concluded with an application of the conceptual insight to conditional thermal states, and the correspondingly tightened maximum work theorem.

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.