Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Moscow University Physics Bulletin

Parallelization of Quantum Algorithms Using Quantum Teleportation

S. S. Sysoev

Published Jun 1, 2025• 0 citations
Publisher

Abstract

Abstract This study proposes a method for parallelizing quantum algorithms in the circuit model based on the technique of quantum gate teleportation. The resulting parallel representation of the algorithm has reduced circuit depth and, consequently, a higher probability of correct execution under conditions of increasing quantum state decoherence over time. The reduction in circuit depth is achieved by increasing circuit width, i.e., the number of qubits simultaneously used in the computation.

DOI
10.3103/s002713492570050x

Related papers

Parallelisation of Quantum Algorithms Using Quantum Teleportation

S. S. Sysoev

This study proposes a method for parallelising quantum algorithms in the circuit model based on the technique of quantum gate teleportation. The resulting parallel representation of the algorithm has reduced circuit depth and, consequently, a higher probability of correct execution under conditions of increasing quantum state decoherence over time. The reduction in circuit depth is achieved by increasing circuit width, i.e. the number of qubits simultaneously used in the computation.

Vestnik Moskovskogo Universiteta Seriya 3 Fizika Astronomiya•Jan 1, 2025•0 citations

Distributed quantum logic algorithm

Boris Arseniev

Parallel computation enables multiple processors to execute different parts of a task simultaneously, improving processing speed and efficiency. In quantum computing, parallel gate implementation involves executing gates independently in different registers, directly impacting the circuit depth, the number of sequential quantum gate operations, and thus the algorithm execution time. This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution, potentially enhancing the performance of quantum simulations on near-term quantum devices. We show that any circuit on $n$ qubits with depth $O\left(M n^2\right)$, where $M = M(n)$ is some function of $n$, can be transformed into a circuit with depth $O\left(\log_2(M) n^2\right)$ operating on $O\left(M n\right)$ qubits. This technique may be particularly useful in noisy environments, where recent findings indicate that only the final $O\left(\log n\right)$ layers influence the expectation value of observables. It may also optimize Trotterization by exponentially reducing the number of Trotter steps. Additionally, the method may offer advantages for distributed quantum computing, and the intuition of treating quantum states as gates and operators as vectors used in this work may have broader applications in quantum computation.

arXiv:2411.11979•Nov 18, 2024•0 citations

Distributed Shor’s Algorithm with Sequential Quantum Teleportation

Jehn‐Ruey Jiang, Ting-Yuan Wang, Wen‐Han Huang +1 more

A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•2 citations

Gate teleportation-assisted routing for quantum algorithms

Aravind Plathanam Babu, Oskari Kerppo, Andrés D. Muñoz-Moller +2 more

Abstract The limited qubit connectivity of quantum processors poses a significant challenge in deploying practical algorithms and logical gates, necessitating efficient qubit mapping and routing strategies. When implementing a gate that requires additional connectivity beyond the native connectivity, the qubit state must be moved to a nearby connected qubit to execute the desired gate locally. This is typically achieved using a series of SWAP gates creating a SWAP path. However, routing methods relying on SWAP gates often lead to increased circuit depth and gate count, motivating the need for alternative approaches. This work explores the potential of teleported gates to improve qubit routing efficiency, focusing on implementation within specific hardware topologies and benchmark quantum algorithms. We propose a routing method that is assisted by gate teleportation. It establishes additional connectivity using gate teleportation paths through available unused qubits, termed auxiliary qubits, within the topology. To optimize this approach, we have developed an algorithm to identify the best gate teleportation connections, considering their potential to reduce the depth of the circuit and address possible errors that may arise from the teleportation paths. Finally, we demonstrate depth reduction with gate teleportation-assisted routing in various benchmark algorithms, including case studies on the compilation of the Deutsch–Jozsa algorithm and the quantum approximation optimization algorithm for heavy-hexagon topology used in IBM 127-qubit Eagle r3 processors. Our benchmark results show a 10%–25% depth reduction in the routing of selected algorithms compared to regular routing without using teleported gates.

arXiv:2502.04138•Quantum Science and Technology•Apr 9, 2025•4 citations

A Parallelized Qubit Mapping Algorithm for Large-scale Quantum Circuits

Dongmin Kim, Sengthai Heng, Youngsun Han

Quantum computers are superior to existing classical supercomputers in terms of run time for specific tasks, and various studies on quantum computers are in progress. Despite this, there is a significant gap in technology between available technologies and actual quantum computers on the noisy intermediate-scale quantum-scale. Currently, various quantum algorithms have been implemented and verified using quantum simulations. Therefore, the runtime performance of a quantum circuit can be verified in the same environment as a real quantum machine. A quantum compiler compiles quantum circuits. When a quantum circuit is compiled, logical qubits in a quantum circuit should be mapped to physical qubits, called qubit mapping. As qubit mapping is an NP-Complete problem, the compilation time increases exponentially according to the number of qubits. Therefore, various studies on effective qubit mapping techniques have been developed to accelerate the execution time. This paper proposes a new parallelized Qubit mapping algorithm. The proposed method consists of three-step processes: one circuit is divided into several circuits; the SABRE enhanced algorithm is executed on each circuit in parallel and then merged. The performance was evaluated using 10 benchmarks. The experimental results revealed an acceleration of up to 6.42x and an average speed up of 4.8x, with an average overhead of 1.03x in terms of the number of gates obtained. The proposed method outperformed the well-known modern qubit-mapping algorithm in terms of the execution time with exponential speedup improvement.

IEIE Transactions on Smart Processing and Computing•Feb 28, 2022•1 citation

Connectivity matrix model of quantum circuits and its application to distributed quantum circuit optimization

Ismail Ghodsollahee, Zohreh Davarzani, Mariam Zomorodi Moghadam +3 more

Abstract As quantum computation grows, the number of qubits involved in a given quantum computer increases. But due to the physical limitations in the number of qubits of a single quantum device, the computation should be performed in a distributed system. In this paper, a new model of quantum computation based on the matrix representation of quantum circuits is proposed. Then, using this model, we propose a novel approach for reducing the number of teleportations in a distributed quantum circuit. The proposed method consists of two phases: the pre-processing phase and the optimization phase. In the pre-processing phase, it considers the bi-partitioning of quantum circuits by Non-Dominated Sorting Genetic Algorithm (NSGA-III) to minimize the number of global gates and to distribute the quantum circuit into two balanced parts with equal number of qubits and minimum number of global gates. In the optimization phase, two heuristics named Heuristic I and Heuristic II are proposed to optimize the number of teleportations according to the partitioning obtained from the pre-processing phase. Finally, the proposed approach is evaluated on many benchmark quantum circuits. The results of these evaluations show an average of 22.16% improvement in the teleportation cost of the proposed approach compared to the existing works in the literature.

Quantum Information Processing•Jul 1, 2021•20 citations
Abstract This study proposes a method for parallelizing quantum algorithms in the circuit model based on the technique of quantum gate teleportation. The resulting parallel representation of the algorithm has reduced circuit depth and, consequently, a higher probability of correct execution under conditions of increasing quantum state decoherence over time. The reduction in circuit depth is achieved by increasing circuit width, i.e., the number of qubits simultaneously used in the computation.
Parallel computation enables multiple processors to execute different parts of a task simultaneously, improving processing speed and efficiency. In quantum computing, parallel gate implementation involves executing gates independently in different registers, directly impacting the circuit depth, the number of sequential quantum gate operations, and thus the algorithm execution time. This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution, potentially enhancing the performance of quantum simulations on near-term quantum devices. We show that any circuit on nnn qubits with depth O(Mn2)O\left(M n^2\right)O(Mn2), where M=M(n)M = M(n)M=M(n) is some function of nnn, can be transformed into a circuit with depth O(log⁡2(M)n2)O\left(\log_2(M) n^2\right)O(log2​(M)n2) operating on O(Mn)O\left(M n\right)O(Mn) qubits. This technique may be particularly useful in noisy environments, where recent findings indicate that only the final O(log⁡n)O\left(\log n\right)O(logn) layers influence the expectation value of observables. It may also optimize Trotterization by exponentially reducing the number of Trotter steps. Additionally, the method may offer advantages for distributed quantum computing, and the intuition of treating quantum states as gates and operators as vectors used in this work may have broader applications in quantum computation.
A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.
Abstract The limited qubit connectivity of quantum processors poses a significant challenge in deploying practical algorithms and logical gates, necessitating efficient qubit mapping and routing strategies. When implementing a gate that requires additional connectivity beyond the native connectivity, the qubit state must be moved to a nearby connected qubit to execute the desired gate locally. This is typically achieved using a series of SWAP gates creating a SWAP path. However, routing methods relying on SWAP gates often lead to increased circuit depth and gate count, motivating the need for alternative approaches. This work explores the potential of teleported gates to improve qubit routing efficiency, focusing on implementation within specific hardware topologies and benchmark quantum algorithms. We propose a routing method that is assisted by gate teleportation. It establishes additional connectivity using gate teleportation paths through available unused qubits, termed auxiliary qubits, within the topology. To optimize this approach, we have developed an algorithm to identify the best gate teleportation connections, considering their potential to reduce the depth of the circuit and address possible errors that may arise from the teleportation paths. Finally, we demonstrate depth reduction with gate teleportation-assisted routing in various benchmark algorithms, including case studies on the compilation of the Deutsch–Jozsa algorithm and the quantum approximation optimization algorithm for heavy-hexagon topology used in IBM 127-qubit Eagle r3 processors. Our benchmark results show a 10%–25% depth reduction in the routing of selected algorithms compared to regular routing without using teleported gates.
Quantum computers are superior to existing classical supercomputers in terms of run time for specific tasks, and various studies on quantum computers are in progress. Despite this, there is a significant gap in technology between available technologies and actual quantum computers on the noisy intermediate-scale quantum-scale. Currently, various quantum algorithms have been implemented and verified using quantum simulations. Therefore, the runtime performance of a quantum circuit can be verified in the same environment as a real quantum machine. A quantum compiler compiles quantum circuits. When a quantum circuit is compiled, logical qubits in a quantum circuit should be mapped to physical qubits, called qubit mapping. As qubit mapping is an NP-Complete problem, the compilation time increases exponentially according to the number of qubits. Therefore, various studies on effective qubit mapping techniques have been developed to accelerate the execution time. This paper proposes a new parallelized Qubit mapping algorithm. The proposed method consists of three-step processes: one circuit is divided into several circuits; the SABRE enhanced algorithm is executed on each circuit in parallel and then merged. The performance was evaluated using 10 benchmarks. The experimental results revealed an acceleration of up to 6.42x and an average speed up of 4.8x, with an average overhead of 1.03x in terms of the number of gates obtained. The proposed method outperformed the well-known modern qubit-mapping algorithm in terms of the execution time with exponential speedup improvement.
Abstract As quantum computation grows, the number of qubits involved in a given quantum computer increases. But due to the physical limitations in the number of qubits of a single quantum device, the computation should be performed in a distributed system. In this paper, a new model of quantum computation based on the matrix representation of quantum circuits is proposed. Then, using this model, we propose a novel approach for reducing the number of teleportations in a distributed quantum circuit. The proposed method consists of two phases: the pre-processing phase and the optimization phase. In the pre-processing phase, it considers the bi-partitioning of quantum circuits by Non-Dominated Sorting Genetic Algorithm (NSGA-III) to minimize the number of global gates and to distribute the quantum circuit into two balanced parts with equal number of qubits and minimum number of global gates. In the optimization phase, two heuristics named Heuristic I and Heuristic II are proposed to optimize the number of teleportations according to the partitioning obtained from the pre-processing phase. Finally, the proposed approach is evaluated on many benchmark quantum circuits. The results of these evaluations show an average of 22.16% improvement in the teleportation cost of the proposed approach compared to the existing works in the literature.