Related papers: Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms

Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms

URL: http://arxiv.org/abs/2106.12517v2
Date: Tue, 29 Jun 2021 17:16:20 GMT
Title: Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
Authors: Fernando R. Cardoso, Daniel Yoshio Akamatsu, Vivaldo Leiria Campo Junior, Eduardo I. Duzzioni, Alfredo Jaramillo Palma and Celso J. Villas-Boas
Abstract summary: 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.
Score: 55.41644538483948
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work, we are interested in the detailed analysis of complexity aspects of both time and space that arises from the implementation of a quantum algorithm on a quantum based hardware. In particular, some steps of the implementation, as state preparation and readout processes, in most of the cases 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, from state preparation to the number of measurements needed to obtain good statistics from the final states of the quantum system, in order to assess the overall complexity of the processes.

Related papers

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 Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z)
Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z)
Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines [0.9374652839580183]
This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM) We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM.
arXiv Detail & Related papers (2023-05-23T17:07:58Z)
Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
We analyze the circuit complexity for preparing ground states of quantum many-body systems. In particular, how this complexity grows as the ground state approaches a quantum phase transition.
arXiv Detail & Related papers (2023-01-11T19:00:10Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z)
End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z)
Efficient Deterministic Preparation of Quantum States Using Decision Diagrams [4.782945936674342]
In this paper, we consider quantum states that can be efficiently represented by (reduced) decision diagrams. We design an algorithm that utilises the structure of decision diagrams to prepare their associated quantum states.
arXiv Detail & Related papers (2022-06-17T07:15:35Z)
Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
arXiv Detail & Related papers (2021-09-23T07:46:20Z)
Large-scale quantum hybrid solution for linear systems of equations [0.0]
We introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup. We solve experimentally a $217$-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers.
arXiv Detail & Related papers (2020-03-28T11:23:05Z)

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