A simple quantum algorithm to efficiently prepare sparse states

• URL: http://arxiv.org/abs/2310.19309v1
• Date: Mon, 30 Oct 2023 07:05:15 GMT
• Title: A simple quantum algorithm to efficiently prepare sparse states
• Authors: Debora Ramacciotti, Andreea-Iulia Lefterovici, Antonio F. Rotundo
• Abstract summary: We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. This is competitive with the best known algorithms for sparse state preparation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper, we analyse the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation

Related papers

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Opening the Black Box Inside Grover's Algorithm [0.0]
  Grover's algorithm is a primary algorithm offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum-inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of calls to (simulations of) the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
  Isomap algorithm is widely used in neuroimaging, spectral analysis and other fields. We propose the quantum Isomap algorithm, which consists of two sub-algorithms. The time complexity of quantum Isomap algorithm is $O(dNpolylogN)$.
  arXiv  Detail & Related papers  (2022-12-07T12:29:41Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Efficient and Local Parallel Random Walks [21.29022677162416]
  Random walks are a fundamental primitive used in many machine learning algorithms. We present a new algorithm that overcomes this limitation by building random walk efficiently and locally. We show that our technique is both memory and round efficient, and in particular yields an efficient parallel local clustering algorithm.
  arXiv  Detail & Related papers  (2021-12-01T17:06:11Z)
• Double sparse quantum state preparation [1.7338677787507775]
  We propose a quantum state preparation algorithm called CVO-QRAM with computational cost O(kM) The proposed algorithm can be an alternative to create sparse states in future NISQ devices.
  arXiv  Detail & Related papers  (2021-08-30T21:32:26Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)

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.