Classical and Quantum Algorithms for the Deterministic L-system Inductive Inference Problem

• URL: http://arxiv.org/abs/2411.19906v2
• Date: Mon, 30 Dec 2024 20:37:49 GMT
• Title: Classical and Quantum Algorithms for the Deterministic L-system Inductive Inference Problem
• Authors: Ali Lotfi, Ian McQuillan, Steven Rayan,
• Abstract summary: L-systems can be made to model and create simulations of many biological processes, such as plant development.<n>Finding an L-system for a given process is typically solved by hand, by experts, in a massively time-consuming process.<n>It would be significant if this could be done automatically from data, such as from sequences of images.
• Score: 1.7068557927955383
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: L-systems can be made to model and create simulations of many biological processes, such as plant development. Finding an L-system for a given process is typically solved by hand, by experts, in a massively time-consuming process. It would be significant if this could be done automatically from data, such as from sequences of images. In this paper, we are interested in inferring a particular type of L-system, deterministic context-free L-system (D0L-system) from a sequence of strings. We introduce the characteristic graph of a sequence of strings, which we then utilize to translate our problem (inferring D0L-system) in polynomial time into the maximum independent set problem (MIS) and the SAT problem. After that, we offer a classical exact algorithm and an approximate quantum algorithm for the problem.

Related papers

• A system identification approach to clustering vector autoregressive time series [50.66782357329375]
  Clustering time series based on their underlying dynamics is keeping attracting researchers due to its impacts on assisting complex system modelling.<n>Most current time series clustering methods handle only scalar time series, treat them as white noise, or rely on domain knowledge for high-quality feature construction.<n>Instead of relying on feature/metric construction, the system identification approach allows treating vector time series clustering by explicitly considering their underlying autoregressive dynamics.
  arXiv  Detail & Related papers  (2025-05-20T14:31:44Z)
• Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
  We present an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) on a digital quantum device. The result is a quantum algorithm avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size. We apply this to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid.
  arXiv  Detail & Related papers  (2024-09-13T15:46:32Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
  We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
  arXiv  Detail & Related papers  (2024-03-28T20:37:32Z)
• Quantum Relaxation for Linear Systems in Finite Element Analysis [0.0]
  We present Quantum Relaxation for Linear System (qRLS) as an iterative approach for gate-based quantum computers. The well-conditioned system enables a practical iterative solution of finite element problems using the state-of-the-art Quantum Signal Processing (QSP) variant of QLSAs. This represents an exponential efficiency gain, offering a new approach for iterative finite element problem-solving on quantum hardware.
  arXiv  Detail & Related papers  (2023-08-02T18:31:33Z)
• Dense outputs from quantum simulations [5.295277584890625]
  The quantum dense output problem is the process of evaluating time-accumulated observables from time-dependent quantum dynamics. This problem arises frequently in applications such as quantum control and spectroscopic computation. We present a range of algorithms designed to operate on both early and fully fault-tolerant quantum platforms.
  arXiv  Detail & Related papers  (2023-07-26T18:16:51Z)
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems [0.2624902795082451]
  We investigate the limitations of quantum computers for solving nonlinear dynamical systems. We provide a significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector.
  arXiv  Detail & Related papers  (2023-07-13T11:06:02Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• Dealing with Collinearity in Large-Scale Linear System Identification Using Gaussian Regression [3.04585143845864]
  We consider estimation of networks consisting of several interconnected dynamic systems. We develop a strategy cast in a Bayesian regularization framework where any impulse response is seen as realization of a zero-mean Gaussian process. We design a novel Markov chain Monte Carlo scheme able to reconstruct the impulse responses posterior by efficiently dealing with collinearity.
  arXiv  Detail & Related papers  (2023-02-21T19:35:47Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
  arXiv  Detail & Related papers  (2021-05-06T08:48:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Analysis of a density matrix renormalization group approach for transport in open quantum systems [0.0]
  Density matrix renormalization group-based tools have been widely used in the study of closed systems. We present an implementation based on state-of-the-art matrix product state (MPS) and tensor network methods. We show that this implementation is suited for studying thermal transport in one-dimensional systems.
  arXiv  Detail & Related papers  (2020-09-17T10:37:49Z)
• Learned Factor Graphs for Inference from Stationary Time Sequences [107.63351413549992]
  We propose a framework that combines model-based algorithms and data-driven ML tools for stationary time sequences. neural networks are developed to separately learn specific components of a factor graph describing the distribution of the time sequence. We present an inference algorithm based on learned stationary factor graphs, which learns to implement the sum-product scheme from labeled data.
  arXiv  Detail & Related papers  (2020-06-05T07:06:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.