Improved distributed quantum algorithm for Simon's problem

• URL: http://arxiv.org/abs/2504.09605v1
• Date: Sun, 13 Apr 2025 14:50:01 GMT
• Title: Improved distributed quantum algorithm for Simon's problem
• Authors: Hao Li, Daowen Qiu,
• Abstract summary: Simon's problem is one of the most important problems demonstrating the power of quantum computing.<n>In this paper, we design an improved distributed quantum algorithm for Simon's problem without using sorting operators.<n>Our algorithm has the advantage of reducing half number of qubits required for a single computing node.
• Score: 8.155532786940858
• 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 computing. Recently, an interesting distributed quantum algorithm for Simon's problem was proposed, where a key sorting operator requiring a large number of qubits was employed. In this paper, we design an improved distributed quantum algorithm for Simon's problem without using sorting operators, and our algorithm has the advantage of reducing half number of qubits required for a single computing node. Moreover, our algorithm does not involve the classical search process.

Related papers

• Simon's Period Finding on a Quantum Annealer [0.0]
  Simon's period-finding algorithm is among the earliest and most fragile of quantum algorithms. We implement this algorithm on D-Wave hardware and solve problems with up to 298 qubits.
  arXiv  Detail & Related papers  (2025-04-15T00:17:13Z)
• 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)
• Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems [0.0]
  Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
  arXiv  Detail & Related papers  (2023-11-16T09:19:01Z)
• Exact distributed quantum algorithm for generalized Simon's problem [8.061563029894927]
  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.
  arXiv  Detail & Related papers  (2023-07-26T17:25:39Z)
• 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)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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 Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• 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.