Quantum Dynamic Programming

• URL: http://arxiv.org/abs/2403.09187v2
• Date: Fri, 14 Feb 2025 06:29:46 GMT
• Title: Quantum Dynamic Programming
• Authors: Jeongrak Son, Marek Gluza, Ryuji Takagi, Nelly H. Y. Ng,
• Abstract summary: We show how to coherently generate step unitaries by using memorized intermediate quantum states.<n> Quantum dynamic programming achieves an exponential reduction in circuit depth for a broad class of fixed-point quantum recursions.<n>We showcase applications of quantum dynamic programming to several quantum recursions, including a variant of Grover's search, quantum imaginary-time evolution, and 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 that efficiently solves recursive problems using memory. Our innovation lies in showing how to coherently generate recursion step unitaries by using memorized intermediate quantum states. Quantum dynamic programming achieves an exponential reduction in circuit depth for a broad class of fixed-point quantum recursions, though this comes at the cost of increased circuit width. Interestingly, the trade-off becomes more favourable when the initial state is pure. By hybridizing our approach with a conventional memoryless one, we can flexibly balance circuit depth and width to optimize performance on quantum devices with fixed hardware constraints. Finally, we showcase applications of quantum dynamic programming to several quantum recursions, including a variant of Grover's search, quantum imaginary-time evolution, and a new protocol for obliviously preparing a quantum state in its Schmidt basis.

Related papers

• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage [17.38734393793605]
  We propose an approximate method for compiling target quantum circuits into brick-wall layouts. This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers.
  arXiv  Detail & Related papers  (2025-01-13T15:04:39Z)
• Circuit Folding: Modular and Qubit-Level Workload Management in Quantum-Classical Systems [5.6744988702710835]
  Circuit knitting is a technique that offloads some of the computational burden from quantum circuits. We propose CiFold, a novel graph-based system that identifies and leverages repeated structures within quantum circuits. Our system has been extensively evaluated across various quantum algorithms, achieving up to 799.2% reduction in quantum resource usage.
  arXiv  Detail & Related papers  (2024-12-24T23:34:17Z)
• 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)
• Parameterized quantum comb and simpler circuits for reversing unknown qubit-unitary operations [8.14510296131348]
  We propose PQComb to harness the full potential of quantum combs for diverse quantum process transformation tasks. We present two streamlined protocols for the time-reversal simulation of unknown qubit unitary evolutions. We also extend PQComb to solve the problems of qutrit unitary transformation and channel discrimination.
  arXiv  Detail & Related papers  (2024-03-06T14:53:24Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• 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)
• Quantum Neural Architecture Search with Quantum Circuits Metric and Bayesian Optimization [2.20200533591633]
  We propose a new quantum gates distance that characterizes the gates' action over every quantum state. Our approach significantly outperforms the benchmark on three empirical quantum machine learning problems.
  arXiv  Detail & Related papers  (2022-06-28T16:23:24Z)
• 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)
• Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years. However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number. This result leads to a general standpoint that deep quantum circuits would not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• 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)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale [57.84751206630535]
  We present a modernized version of the Quantum Virtual Machine (TNQVM) which serves as a quantum circuit simulation backend in the e-scale ACCelerator (XACC) framework. The new version is based on the general purpose, scalable network processing library, ExaTN, and provides multiple quantum circuit simulators. By combining the portable XACC quantum processors and the scalable ExaTN backend we introduce an end-to-end virtual development environment which can scale from laptops to future exascale platforms.
  arXiv  Detail & Related papers  (2021-04-21T13:26:42Z)
• 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.