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

• 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)
• Taming Quantum Time Complexity [50.10645865330582]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.