Exact distributed quantum algorithm for generalized Simon's problem

• URL: http://arxiv.org/abs/2307.14315v1
• Date: Wed, 26 Jul 2023 17:25:39 GMT
• Title: Exact distributed quantum algorithm for generalized Simon's problem
• Authors: Hao Li, Daowen Qiu, Le Luo, Mateus Paulo
• Abstract summary: Simon's problem is one of the most important problems demonstrating the power of quantum algorithms. We introduce a corresponding distributed quantum algorithm for Simon's problem. We refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique.
• Score: 8.061563029894927
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Simon's problem is one of the most important problems demonstrating the power of quantum algorithms, as it greatly inspired the proposal of Shor's algorithm. The generalized Simon's problem is a natural extension of Simon's problem, and also a special hidden subgroup problem. In this paper, we present two key contributions. Firstly, we characterize the structure of the generalized Simon's problem in distributed scenario and introduce a corresponding distributed quantum algorithm. Secondly, we refine the algorithm to ensure exactness due to the application of quantum amplitude amplification technique. Our algorithm offers exponential acceleration compared to the distributed classical algorithm. When contrasted with the centralized quantum algorithm for the generalized Simon's problem, our algorithm's oracle requires fewer qubits, thus making it easier to be physically implemented. Particularly, the exact distributed quantum algorithm we develop for the generalized Simon's problem outperforms the best previously proposed distributed quantum algorithm for Simon's problem in terms of generalizability and exactness.

Related papers

• Simon's algorithm in the NISQ cloud [0.0]
  Simon's algorithm was one of the first problems to demonstrate a genuine quantum advantage. We use Simon's algorithm to benchmark the error rates of devices currently available in the "quantum cloud"
  arXiv  Detail & Related papers  (2024-06-17T17:31:44Z)
• Simon algorithm in measurement-based quantum computing [0.0]
  Simon's subgroup hidden algorithm was the first quantum algorithm to prove the superiority of quantum computing over classical computing. We present a reformulation of the Simon algorithm into the language of measurement-based quantum computing. We show that the $n$-qubit version of the Simon algorithm can be formulated in MBQC as cluster state graph with $2n$ nodes and $n2$ edges.
  arXiv  Detail & Related papers  (2024-05-28T13:02:54Z)
• 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)
• Feasibility Analysis of Grover-meets-Simon Algorithm [4.826899218632946]
  Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm.
  arXiv  Detail & Related papers  (2023-01-17T05:13:36Z)
• 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)
• Distributed quantum algorithm for Simon's problem [2.26741603346646]
  We study the Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits.
  arXiv  Detail & Related papers  (2022-04-25T01:22:22Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)
• 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)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)
• Quantum Bandits [10.151012770913622]
  We consider the quantum version of the bandit problem known as em best arm identification (BAI) We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum. We then propose an algorithm based on quantum amplitude amplification to solve BAI.
  arXiv  Detail & Related papers  (2020-02-15T15:17:11Z)

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.