Quantum Dynamic Programming

• URL: http://arxiv.org/abs/2403.09187v1
• Date: Thu, 14 Mar 2024 08:59:22 GMT
• Title: Quantum Dynamic Programming
• Authors: Jeongrak Son, Marek Gluza, Ryuji Takagi, Nelly H. Y. Ng,
• Abstract summary: We show how to coherently generate unitaries of recursion steps using memorized intermediate quantum states. We find that quantum dynamic programming yields an exponential reduction in circuit depth for a large class of fixed-point quantum recursions. We apply quantum dynamic programming to a recently proposed double-bracket quantum algorithm for diagonalization to obtain a new protocol for obliviously preparing a quantum state in its Schmidt basis.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a quantum extension of dynamic programming, a fundamental computational method for efficiently solving recursive problems using memory. Our innovation lies in showing how to coherently generate unitaries of recursion steps using memorized intermediate quantum states. We find that quantum dynamic programming yields an exponential reduction in circuit depth for a large class of fixed-point quantum recursions, including a known recursive variant of the Grover's search. Additionally, we apply quantum dynamic programming to a recently proposed double-bracket quantum algorithm for diagonalization to obtain a new protocol for obliviously preparing a quantum state in its Schmidt basis, providing a potential pathway for revealing entanglement structures of unknown quantum states.

Related papers

• Exploiting recursive structures for the design of novel quantum primitives [0.1227734309612871]
  This paper focuses on generating novel quantum primitives. We show how these structures can be exploited to design new, potentially advantageous quantum algorithms. We comment on the potential impact on quantum algorithms, numerical analysis, and signal processing.
  arXiv  Detail & Related papers  (2024-10-17T17:45:50Z)
• 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)
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs [7.042810171786408]
  We propose a notion of quantum register machine, the first purely quantum architecture (including an instruction set) that supports quantum control flows. Based on quantum register machine, we describe the first comprehensive implementation process of quantum recursion programs. Our efficient implementation of quantum algorithms also offers automatic parallelisation of quantum algorithms.
  arXiv  Detail & Related papers  (2024-08-19T14:48:41Z)
• Feedback-Based Quantum Algorithm for Excited States Calculation [0.6554326244334868]
  We propose a new design methodology that combines the layer-wise construction of the quantum circuit in feedback-based quantum algorithms with a new feedback law based on a new Lyapunov function to assign the quantum circuit parameters. We demonstrate the algorithm through an illustrative example and through an application in quantum chemistry.
  arXiv  Detail & Related papers  (2024-04-06T12:51:17Z)
• Quantum Recursive Programming with Quantum Case Statements [8.320147245667124]
  A simple programming language for supporting this kind of quantum recursion is defined. A series of examples are presented to show that some quantum algorithms can be elegantly written as quantum recursion programs.
  arXiv  Detail & Related papers  (2023-11-03T05:44:52Z)
• Double-bracket quantum algorithms for diagonalization [0.0]
  This work proposes double-bracket iterations as a framework for obtaining diagonalizing quantum circuits. Their implementation on a quantum computer consists of interlacing evolutions generated by the input Hamiltonian with diagonal evolutions which can be chosen variationally.
  arXiv  Detail & Related papers  (2022-06-23T15:13:46Z)
• An Introduction to Quantum Machine Learning for Engineers [36.18344598412261]
  Quantum machine learning is emerging as a dominant paradigm to program gate-based quantum computers. This book provides a self-contained introduction to quantum machine learning for an audience of engineers with a background in probability and linear algebra.
  arXiv  Detail & Related papers  (2022-05-11T12:10:52Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• The Hintons in your Neural Network: a Quantum Field Theory View of Deep Learning [84.33745072274942]
  We show how to represent linear and non-linear layers as unitary quantum gates, and interpret the fundamental excitations of the quantum model as particles. On top of opening a new perspective and techniques for studying neural networks, the quantum formulation is well suited for optical quantum computing.
  arXiv  Detail & Related papers  (2021-03-08T17:24:29Z)
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator [41.74498230885008]
  We demonstrate a programmable quantum simulator based on deterministically prepared two-dimensional arrays of neutral atoms. We benchmark the system by creating and characterizing high-fidelity antiferromagnetically ordered states. We then create and study several new quantum phases that arise from the interplay between interactions and coherent laser excitation.
  arXiv  Detail & Related papers  (2020-12-22T19:00:04Z)

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.