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.
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.
Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).
Abstract Distributed quantum computation has gained significant interest in the noisy intermediate‐scale quantum (NISQ) era. This paradigm requires each computing node to possess a reduced number of qubits and quantum gates. In this study, a Distributed Simon's Algorithm (DSA) is designed to tackle Simon's problem, which entails the discovery of a hidden string of a promised Boolean function , where if and only if or . Specifically, 1) our algorithm is capable of being partitioned into any nodes, where ; 2) the number of queries required by the DSA is , while that of the original Simon's algorithm (SA) is ; 3) the maximum number of qubits required by our approach at a single node is , which is fewer than the qubits required by both the SA and existing distributed Simon's algorithm. Here, denotes the number of computing qubits needed for the ‐th node and satisfies ; 4) the optimal circuit depth of the DSA is , which is reduced compared to the circuit depth of the SA, ; 5) in contrast to currently distributed schemes, the DSA eliminates the need for classical queries; 6) how the DSA solves a specific Simon's problem (e.g., ) is also simulated using MindSpore Quantum, a quantum simulation software. The simulation results show that the DSA features a shallower quantum circuit, thereby demonstrating enhanced resistance to circuit noise. This characteristic makes it more feasible for implementation in the NISQ era.
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: Given a function f : {0, 1} n → {0, 1} m , with the property that for any x, y ∈ {0, 1} n , there is some unknown hidden subgroup S ≤ Z n 2 such that f (x) = f (y) iff x ⊕ y ∈ S, where |S| = 2 k for some 0 ≤ k ≤ n (m ≥ n − k). The goal of generalized Simon’s problem is to find the hidden subgroup S. 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. Particulary, 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.
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate s/r, where r is the ``order" and s is some natural number that less than r. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2 qubits for factoring an L-bit integer and reduces the circuit depth of each computer.
This article presents an algorithm for fast factorization on quantum computer. Quantum mechanic introduces to information processing new effects that can be used to solve efficiently problems classical known as hard. Simon algorithm was one of the first proofs that quantum computer has some advantages over classical model of computation. Shor generalized ideas introduce by Simon and show that real world problems are in range of quantum computation. Article presents also general description of quantum Fourier transform (QFT), which is without doubt the most powerful tool used in algorithms described in this paper. Generalization of algorithms for Simon problem and fast factorization gives new class of problems for which fast quantum algorithms can be construct.
Multi-objective search means searching for any one of several objectives in an unstructured database. Grover's algorithm has quadratic acceleration in multi-objection search than classical ones. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification. In this paper, we design two distributed iterated operators and therefore two new distributed Grover's algorithms are obtained with the following advantages: (1) Compared to Grover's algorithm and the modified Grover's algorithm by Long, our distributed algorithms require fewer qubits; (2) Compared to the distributed Grover's algorithm proposed by Qiu et al., one of our distributed algorithms is exact. Of course, both our distributed algorithms require quite quantum communication and involve a number of more complicated unitary operators as cost, but there still may have certain advantage of physical realizability in the Noisy Intermediate-Scale Quantum (NISQ) era.