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. 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.
• Score: 1.7068557927955383
• License:
• 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

• 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)
• 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)

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.