Physics of Information Processing and Complexity

Analog variational quantum algorithm (VQA) is an experimentally feasible approach to realize quantum optimization algorithms using native quantum dynamics. By exploiting the physics of many-body localization (MBL), analog VQA can be trained at initialization at scale, unlike thermalized phases whose quenched evolutions suffer from untrainability (an exponentially flat optimization landscape). This concept is parallel to expressivity-induced barren plateaus and warm-start initialization strategy in gate-based VQAs.

The scalability barriers in VQAs fundamentally arise from quantum-to-classical information extraction, namely the exponential concentration of observable readouts leading to exponentially vanishing loss gradients. A crucial question is then: Can we design efficient, coherent protocols for optimization and learning without a quantum-to-classical feedback loop? We investigate two such approaches.

Imaginary-time evolution (ITE) suppresses high-energy components of a quantum state and thus provides an alternative for ground-state preparation and optimization. We show that even when this energy-filtering process can operate coherently on a quantum hardware, ITE is fundamentally limited by stagnation and false convergence phenomena, where energy decay can slow down and stagnate near some excited states. Overcoming these limitations would allow ITE to accelerate optimization protocols.

Riemannian gradient descent follows directions of steepest descent that respect the geometry of unitary transformations. Such unitary updates can be approximated by quantum circuits from double-bracket quantum algorithms. For suitable loss functions and with access to the required quantum operations, this provides an autonomous quantum machine learning framework in which training proceeds coherently without intermediate quantum measurements or classical feedback. This approach can perform quantum phase classification and unitary learning that exploits symmetries inherited from the training data without explicitly imposing them. A central challenge is circuit depth, which grows rapidly with the number of training iterations.

Reliable quantum information processing requires confidence that a device has prepared the targeted state. Full many-qubit tomography is generally impractical, motivating certification tests with rigorous guarantees. We study certification of pure fermionic Gaussian states, including Slater determinants and BCS pairing states, which are important reference states for quantum simulations of electronic structure and many-body physics. Building on the certification protocols of Huang, Preskill, and Soleimanifar, we develop a protocol using single-qubit measurements that achieves optimal sample complexity scaling of 1/ε, with the allowed infidelity ε at fixed system size and confidence. The analysis relates this sample complexity to the inverse spectral gap of an associated classical Markov chain, and connects fermionic Gaussian state certification to relaxation toward equilibrium in networks.