The computational advantage of quantum algorithms over classical algorithmshas been partially proven, but its deep connection with the dynamics of open quantum systems has yet to be elucidated. This paper establishes a formal correspondence between quantum algorithm complexity and dissipative dynamics based onthe framework of Quantum Iterated Function Systems (QIFS). We first prove thatthe convergence rate of a QIFS—governed by the spectral gap ∆—directly determines the query complexity and time complexity of the corresponding quantumalgorithm. Second, we establish an exponential relationship between the quantumgroup parameter q and the success probability of the algorithm, revealing the dualrole played by decoherence in quantum search algorithms: moderate decoherenceaccelerates convergence, while excessive decoherence causes the algorithm to fail.Building on this, we propose the “dissipative speedup” theorem: there exists an optimal decoherence rate Γopt such that the quantum algorithm described by the QIFSachieves minimal time complexity, and this optimal value satisfies Γopt = −lnq/tc.Finally, we explore the connections between this framework and adiabatic quantum computation as well as quantum walk algorithms, and propose experimentalschemes to test the theoretical predictions on superconducting quantum processors.This work unifies the theory of open quantum systems, quantum group algebra,and quantum computational complexity into a common generative framework, providing a new perspective for understanding the persistence of quantum advantagein noisy environments.
The computational advantage of quantum algorithms over classical algorithmshas been partially proven, but its deep connection with the dynamics of open quantum systems has yet to be elucidated. This paper establishes a formal correspondence between quantum algorithm complexity and dissipative dynamics based onthe framework of Quantum Iterated Function Systems (QIFS). We first prove thatthe convergence rate of a QIFS—governed by the spectral gap ∆—directly determines the query complexity and time complexity of the corresponding quantumalgorithm. Second, we establish an exponential relationship between the quantumgroup parameter q and the success probability of the algorithm, revealing the dualrole played by decoherence in quantum search algorithms: moderate decoherenceaccelerates convergence, while excessive decoherence causes the algorithm to fail.Building on this, we propose the “dissipative speedup” theorem: there exists an optimal decoherence rate Γopt such that the quantum algorithm described by the QIFSachieves minimal time complexity, and this optimal value satisfies Γopt = −lnq/tc.Finally, we explore the connections between this framework and adiabatic quantum computation as well as quantum walk algorithms, and propose experimentalschemes to test the theoretical predictions on superconducting quantum processors.This work unifies the theory of open quantum systems, quantum group algebra,and quantum computational complexity into a common generative framework, providing a new perspective for understanding the persistence of quantum advantagein noisy environments.
This paper establishes a rigorous correspondence between quantum generativedynamics and quantum algorithmic complexity, reducing the query complexity andtime complexity of algorithms to the spectral properties of the generative process.Byembedding quantum algorithms within the framework of quantum iterated function systems, it is proven that the convergence rate of an algorithm is uniquely determined by the spectral gap ∆ of the Markov operator: the required number of iterations T ∼ (1/∆)ln(1/ε). Furthermore, the dual role of decoherence in quantumsearch is revealed-the competition between coherent and dissipative contributionsleads to the existence of an optimal decoherence rate, given by Γopt ∼ −(1/4)lnN,which corresponds to the optimal complexity of Grover’s algorithm. By relatingthe spectral gap to the quantum group parameter q = e−Γtc, we derive ∆ = 1−q2,establishing a direct correspondence between algebraic parameters and computational resources. This framework unifies open quantum system theory, quantumgroup algebra, and quantum computational complexity under the language of generative dynamics, providing a new theoretical foundation for understanding thebehavior of quantum algorithms in noisy environments.
We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.
A quantum system that has interaction with external resources, such as probability distribution, dissipation, and noise, is referred to as an open quantum system. Not only do open quantum systems play a vital role in the field of quantum physics, but they are also fundamental objects in quantum information and quantum computing. In this thesis, we focus on computational problems related to open quantum systems. In particular, we study efficient constructions of open quantum systems and their algorithmic applications. \n \nA unitary 2-design is a quantum analogue of universal 2-hash functions. It is an example of open quantum systems in the sense that it is a probability distribution of unitaries. As unitary 2-designs inherit many properties of the Haar randomness on the unitary group, they have many applications in quantum information, such as benchmarking and decoupling. We study the structures of unitary 2-designs and present efficient methods for their constructions. \n \nThe continuous-time evolution of a closed quantum system can be described by the Schrödinger equation. A natural generalization of the Schrödinger equation to Markovian open quantum systems, in the sense of generating dynamical semigroups, is called the Lindblad equation. We show that it is impossible for a simple reductionist approach to simulate Lindblad evolution with gate complexity that has linear dependence in evolution time. Moreover, we use a novel variation of the "linear combination of unitaries" construction that pertains to quantum channels to achieve the desired linear dependence in evolution time and poly-logarithmic dependence in precision. \n \nOpen quantum systems can also be used as building blocks of quantum algorithms. We present a dissipative query model, which is based on the amplitude damping process. With this dissipative query model, we provide a quantum algorithm that performs a fixed-point quantum search while preserving the quadratic speedup against classical algorithms.
Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern technique of theoretical computer science, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the adiabatic theorem, as it goes by constructing a universal adiabatic quantum query algorithm. Another originality is that we use for the first time in the context of quantum computation a version of the adiabatic theorem that does not require a spectral gap.
Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern theoretical computer science technique, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the Adiabatic theorem, as we construct an optimal adiabatic quantum query algorithm.