Approximative lookup-tables and arbitrary function rotations for
facilitating NISQ-implementations of the HHL and beyond
- URL: http://arxiv.org/abs/2306.05024v1
- Date: Thu, 8 Jun 2023 08:22:41 GMT
- Title: Approximative lookup-tables and arbitrary function rotations for
facilitating NISQ-implementations of the HHL and beyond
- Authors: Petros Stougiannidis, Jonas Stein, David Bucher, Sebastian Zielinski,
Claudia Linnhoff-Popien, Sebastian Feld
- Abstract summary: We propose a circuit approximation technique that enhances the arithmetic subroutines in the HHL.
We show how these types of circuits can be reduced in depth by providing a simple and powerful approximation technique.
- Score: 6.1003703380200545
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many promising applications of quantum computing with a provable speedup
center around the HHL algorithm. Due to restrictions on the hardware and its
significant demand on qubits and gates in known implementations, its execution
is prohibitive on near-term quantum computers. Aiming to facilitate such
NISQ-implementations, we propose a novel circuit approximation technique that
enhances the arithmetic subroutines in the HHL, which resemble a particularly
resource-demanding component in small-scale settings. For this, we provide a
description of the algorithmic implementation of space-efficient rotations of
polynomial functions that do not demand explicit arithmetic calculations inside
the quantum circuit. We show how these types of circuits can be reduced in
depth by providing a simple and powerful approximation technique. Moreover, we
provide an algorithm that converts lookup-tables for arbitrary function
rotations into a structure that allows an application of the approximation
technique. This allows implementing approximate rotation circuits for many
polynomial and non-polynomial functions. Experimental results obtained for
realistic early-application dimensions show significant improvements compared
to the state-of-the-art, yielding small circuits while achieving good
approximations.
Related papers
- Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
We develop a reinforcement learning-based quantum compiler for a superconducting processor.
We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths.
Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
arXiv Detail & Related papers (2024-06-18T01:49:48Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs.
USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
arXiv Detail & Related papers (2023-12-19T02:27:22Z) - Reinforcement Learning Based Quantum Circuit Optimization via ZX-Calculus [0.0]
We propose a novel Reinforcement Learning (RL) method for optimizing quantum circuits using graph-theoretic simplification rules of ZX-diagrams.
We demonstrate the capacity of our approach by comparing it against the best performing ZX-Calculus-based algorithm for the problem in hand.
Our approach is ready to be used as a valuable tool for the implementation of quantum algorithms in the near-term intermediate-scale range (NISQ)
arXiv Detail & Related papers (2023-12-18T17:59:43Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties.
We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
arXiv Detail & Related papers (2023-10-18T10:29:58Z) - Provable Advantage of Parameterized Quantum Circuit in Function
Approximation [17.286013304279013]
We analyze the expressivity of PQCs through the lens of function approximation.
We compare our proposed PQCs to nearly optimal deep neural networks in approxing high-dimensional smooth functions.
arXiv Detail & Related papers (2023-10-11T14:29:11Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation.
Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions.
We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
arXiv Detail & Related papers (2023-07-08T15:41:48Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs)
We propose a new protocol for approximating TN states using realistic quantum circuits.
Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
arXiv Detail & Related papers (2022-09-01T17:08:41Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Performance Evaluations of Noisy Approximate Quantum Fourier Arithmetic [1.1140384738063092]
We implement QFT-based integer addition and multiplications on quantum computers.
These operations are fundamental to various quantum applications.
We evaluate these implementations based on IBM's superconducting qubit architecture.
arXiv Detail & Related papers (2021-12-17T06:51:18Z) - Deterministic Algorithms for Compiling Quantum Circuits with Recurrent
Patterns [0.0]
Current quantum processors are noisy, have limited coherence and imperfect gate implementations.
We present novel deterministic algorithms for compiling recurrent quantum circuit patterns in time.
Our solution produces unmatched results on RyRz circuits.
arXiv Detail & Related papers (2021-02-17T13:59:12Z) - ACSS-q: Algorithmic complexity for short strings via quantum accelerated
approach [1.4873907857806357]
We present a quantum circuit for estimating algorithmic complexity using the coding theorem method.
As a use-case, an application framework for protein-protein interaction based on algorithmic complexity is proposed.
arXiv Detail & Related papers (2020-09-18T14:41:41Z)
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.