skip to main content

Search for: All records

Creators/Authors contains: "Sone, Akira"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    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.

  2. 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.