arXiv:2609.37802
Quantum Complexity of Ancilla-Free Unitary Embeddings for Nonlinear Dynamics via Generalized State-Dependent Double-Bracket Flows
Yuki Ito, Hideaki Hakoshima, Keisuke Fujii
Abstract
Simulating nonlinear dynamics with quantum computers has gained increasing attention. In general, such simulations require additional quantum resources because unitary quantum evolution is linear. A fundamental question is how nonlinear dynamics can be embedded into fully coherent, ancilla-free unitary circuits and how the complexity of the dynamics governs the required quantum resources. In this work, we generalize the ancilla-free double-bracket quantum algorithm for imaginary-time evolution by replacing its state-independent Hamiltonian with a state-dependent Hermitian operator. Our framework recursively calls an initial state preparation oracle and its inverse, and prepares the target solution to any prescribed accuracy using a fully coherent, ancilla-free unitary embedding. We relate the query cost to the complexity of the nonlinear dynamics, specifically their sensitivity to initial conditions. We obtain query upper bounds of $\exp(O(T))$, $\exp(O(T^2))$, and $\exp(\exp(O(T)))$ when the distance between solutions contracts at least exponentially (contractive), does not increase (nonexpansive), or grows at most exponentially (expansive), respectively, where $T$ is the target evolution time. For the discrete Gross--Pitaevskii equation, our ancilla-free double-bracket circuit achieves optimal worst-case query complexity $Θ(e^{gT/2})$ over a specified family of single-qubit initial states, where $g>0$ is the nonlinearity strength. These results connect the complexity of nonlinear dynamics to the query cost of coherent quantum simulation and provide a foundation for designing ancilla-free unitary embeddings with optimal query complexity.
AI Summary
The paper asks how nonlinear pure-state dynamics can be simulated by fully coherent, ancilla-free circuits, and how sensitivity to initial conditions affects state-preparation query costs. It extends double-bracket quantum imaginary-time evolution to state-dependent Hermitian generators, $\dot\rho=[[\rho,G(\rho)],\rho]$, including nonlinear Schrödinger equations. The construction recursively uses a current state-preparation circuit and its inverse to implement projector exponentials and approximate one-step propagators. Boundedness and Lipschitz assumptions yield $O(\tau^2)$ local error; a trace-norm stability bound controls error accumulation. With fixed model parameters and constant subroutine query cost per update, the initial-oracle query upper bounds are $\exp(O(T/\epsilon))$ for exponentially contractive dynamics, $\exp(O(T^2/\epsilon))$ for nonexpansive dynamics, and $\exp(O(Te^{\lambda T}/\epsilon))$ when distances grow at most as $e^{\lambda t}$. For the discrete Gross–Pitaevskii equation, a small-bias-set approximation to dephasing gives query complexity polynomial in $n=\log_2N$ at fixed time, accuracy, and bounded model parameters. For a specified single-qubit initial-state family, distinguishability amplification establishes an $\Omega(e^{gT/2})$ worst-case lower bound. Trajectory-dependent error estimates improve the recursive simulator’s upper bound to $\exp(O(T^2))$ at fixed strength and accuracy. A separate exact-solution-tailored, Grover-type reflection circuit achieves $\Theta(e^{gT/2})$ worst-case queries. The general bounds assume ancilla-free access to suitable state-dependent operator exponentials and count initial-state oracle queries rather than total gates. Optimality is restricted to the specified two-candidate family with a known family parameter; broader optimal constructions and explicitly time-dependent generators remain open.
They were also used extensively to draft and revise the entire manuscript, including the mathematical proofs.
Error found: The abstract omits the general framework's essential assumption that suitable state-dependent generator exponentials can be implemented coherently without ancillas using preparation-oracle access. The abstract's time-only query bounds require fixed accuracy, fixed model constants, and uniformly bounded per-update oracle usage, conditions explicitly imposed in the body but absent from the abstract. The improved imaginary-time query bound additionally assumes, without proving, that the implemented iterates remain in the subset on which contraction is established.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 23 pages, 1 figure