Near a detailed-balance equilibrium, the perturbed mass-action dynamics of a chemical reaction network (CRN) map exactly onto an electrical-flow problem on the bipartite species-reaction graph: chemical potentials become electrical potentials, Onsager coefficients become conductances, and the instantaneous Gibbs free-energy consumption equals the dissipated electrical energy. We exploit this map to design quantum walk algorithms that decide species reachability, sample reachable species, approximate any individual steady-state reaction flux, and estimate the total Gibbs dissipation. The first three follow from standard electrical-flow quantum walks; the last is non-trivial because the chemical flow is not the minimum-energy electrical flow on the same graph. We resolve this via a new use of alternative neighbourhoods in multidimensional quantum walks, which forces the walker onto the mass-action flow whenever the network is $σ-M$ rigid. In an adjacency-matrix QRAM access model the algorithms achieve up to a quadratic speedup over classical methods -- for example $Ω(n^{3/2})$ vs $Ω(n^2)$ for reachability -- and dissipation-aware bounds tighten this further when the perturbation is concentrated.
Near a detailed-balance equilibrium, the perturbed mass-action dynamics of a chemical reaction network (CRN) map exactly onto an electrical-flow problem on the bipartite species-reaction graph: chemical potentials become electrical potentials, Onsager coefficients become conductances, and the instantaneous Gibbs free-energy consumption equals the dissipated electrical energy. We exploit this map to design quantum walk algorithms that decide species reachability, sample reachable species, approximate any individual steady-state reaction flux, and estimate the total Gibbs dissipation. The first three follow from standard electrical-flow quantum walks; the last is non-trivial because the chemical flow is not the minimum-energy electrical flow on the same graph. We resolve this via a new use of alternative neighbourhoods in multidimensional quantum walks, which forces the walker onto the mass-action flow whenever the network is σ−M rigid. In an adjacency-matrix QRAM access model the algorithms achieve up to a quadratic speedup over classical methods -- for example Ω(n3/2) vs Ω(n2) for reachability -- and dissipation-aware bounds tighten this further when the perturbation is concentrated.
Anderson, Craciun, and Kurtz have proved that a stochastically modelled chemical reaction system with mass-action kinetics admits a stationary distribution when the deterministic model of the same system with mass-action kinetics admits an equilibrium solution obeying a certain complex balance condition. Here we present a proof of their theorem using tools from the theory of second quantization: Fock space, annihilation and creation operators, and coherent states. This is an example of stochastic mechanics, where we take techniques from quantum mechanics and replace amplitudes by probabilities.
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
The Chemical Master Equation (CME) provides a highly accurate yet extremely resource-intensive representation of stochastic chemical reaction networks and their kinetics due to the exponential scaling of its possible states with the number of reacting species. In this work, we investigate how quantum computing can be employed to model stochastic chemical kinetics as described by the CME using the Schlögl model of a trimolecular reaction network as an illustrative example. We analyze the mono- and bistable regimes of the Schlögl model, identifying the bistable regime as more suitable for quantum computation due to the availability of a Hermitian operator form that preserves eigenvalues and eigenvectors. Employing the Variational Quantum Deflation (VQD) algorithm, we compute the smallest-magnitude eigenvalues, λ0, and λ1. We use VQD and a combination of Quantum Phase Estimation (QPE) and Variational Quantum Singular Value Decomposition (VQSVD) to estimate the zeromode (non-equilibrium steady state) of the bistable case. Our results from noiseless quantum simulations (VQD) and quantum hardware (QPE + VQSVD) agree within a few percent with the classically computed eigenvalues and zeromodes of up to 4-qubit operators. We show that achieving an exact solution requires at least 5 qubits, which is within reach of near-term quantum computers.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
A three-dimensional model of binary chemical reactions is studied. We consider an ab initio quantum two-particle system subjected to an attractive interaction potential and to a heat bath at thermal equilibrium at absolute temperature T > 0 . Under the sole action of the attraction potential, the two particles can either be bound or unbound to each other. While at T = 0 , there is no transition between both states, such a transition is possible when T > 0 (due to the heat bath) and plays a key role as k B T approaches the magnitude of the attractive potential. We focus on a quantum regime, typical of chemical reactions, such that: (a) the thermal wavelength is shorter than the range of the attractive potential (lower limit on T) and (b) ( 3 / 2 ) k B T does not exceed the magnitude of the attractive potential (upper limit on T). In this regime, we extend several methods previously applied to analyze the time duration of DNA thermal denaturation. The two-particle system is then described by a non-equilibrium Wigner function. Under Assumptions (a) and (b), and for sufficiently long times, defined by a characteristic time scale D that is subsequently estimated, the general dissipationless non-equilibrium equation for the Wigner function is approximated by a Smoluchowski-like equation displaying dissipation and quantum effects. A comparison with the standard chemical kinetic equations is made. The time τ required for the two particles to transition from the bound state to unbound configurations is studied by means of the mean first passage time formalism. An approximate formula for τ, in terms of D and exhibiting the Arrhenius exponential factor, is obtained. Recombination processes are also briefly studied within our framework and compared with previous well-known methods.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.