The Bitter Truth About Quantum Algorithms in the NISQ Era

• URL: http://arxiv.org/abs/2006.02856v2
• Date: Sat, 6 Jun 2020 09:46:05 GMT
• Title: The Bitter Truth About Quantum Algorithms in the NISQ Era
• Authors: Frank Leymann, Johanna Barzen
• Abstract summary: We discuss factors contributing to the depth and width as well as to the noise of an implementation of an algorithm. Our contribution will help developers in charge of realizing algorithms on such machines in achieving an executable implementation.
• Score: 0.6091702876917281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Implementing a quantum algorithm on a NISQ device has several challenges that arise from the fact that such devices are noisy and have limited quantum resources. Thus, various factors contributing to the depth and width as well as to the noise of an implementation of an algorithm must be understood in order to assess whether an implementation will execute successfully on a given NISQ device. In this contribution, we discuss these factors and their impact on algorithm implementations. Especially, we will cover state preparation, oracle expansion, connectivity, circuit rewriting, and readout: these factors are very often ignored when presenting an algorithm but they are crucial when implementing such an algorithm on near-term quantum computers. Our contribution will help developers in charge of realizing algorithms on such machines in (i) achieving an executable implementation, and (ii) assessing the success of their implementation on a given machine.

Related papers

• Identifying Bottlenecks of NISQ-friendly HHL algorithms [0.0]
  We study noise resilience of NISQ-adaptation Iterative QPE and its HHL algorithm. Results indicate that noise mitigation techniques, such as Qiskit readout and Mthree readout packages, are insufficient for enabling results recovery even in the small instances tested here.
  arXiv  Detail & Related papers  (2024-06-10T14:11:27Z)
• Modelling the Impact of Quantum Circuit Imperfections on Networks and Computer Applications [0.31908919831471466]
  Post Quantum and Quantum Cryptography schemes are feasible quantum computer applications for 7G networks. These algorithms have been compromised by advances in quantum search algorithms run on quantum computers like Shor algorithm.
  arXiv  Detail & Related papers  (2024-03-27T10:00:35Z)
• 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 Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Clever Design, Unexpected Obstacles: Insights on Implementing a Quantum Boltzmann Machine [1.516865739526702]
  We have implemented a gated-based quantum version of a restricted Boltzmann machine for approximating the ground state of a Pauli-decomposed qubit Hamiltonian. We systematically summarize our findings and categorize them according to their relevance for the implementation of similar quantum algorithms.
  arXiv  Detail & Related papers  (2023-01-31T15:29:16Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  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.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm [1.2354542488854734]
  We present a noise-aware qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on a NISQ device, but does not route qubits during the quantum algorithm's execution) We find that for small, connected-graph algorithms, our-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms.
  arXiv  Detail & Related papers  (2021-03-29T15:29:10Z)
• Noisy intermediate-scale quantum (NISQ) algorithms [0.5325753548715747]
  A universal fault-tolerant quantum computer that can solve efficiently problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement towards realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e. qubits that are not error-corrected, and therefore perform imperfect operations in a limited coherence time.
  arXiv  Detail & Related papers  (2021-01-21T05:27:34Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.