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

Physical Review A

Quantum network optimization

Alexandre Blais

Published Jul 1, 2001• 21 citations
Publisher

Abstract

In many candidate designs of solid-state quantum computers, interactions between qubits are limited to a small number of neighboring qubits. Taking into account this limitation we describe how quantum algorithms can be executed efficiently on these designs. We illustrate our results with the quantum Fourier transform for which linear depth networks are obtained. The concepts presented in this work can be applied to all quantum algorithms to reduce considerably the coherence time needed for their execution.

DOI
10.1103/physreva.64.022312

Related papers

Quantum algorithm in quantum network systems

I. Sakamoto

Recently, the quantum computer (QC) using the nano‐devices have significantly attracted attention, because a large‐scale extention of the qubits could be easily realized in the nano‐devices. However, some problems for the realization of the QC with nano‐devices arise from the short decoherence time and the interaction of qubits only between nearest‐neighbor qubits. Therefore, we try to design the optimal quantum circuit of the quantum Fourier transform in various network system by means of the genetic algorithm (GA).

AIP conference proceedings•Jan 1, 2004•0 citations

On the need for large Quantum depth

Nai-Hui Chia, Kai-Min Chung, Ching–Yi Lai

Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation.

ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•20 citations

The quantum Fourier transform on a linear nearest neighbor architecture

Yasuhiro Takahashi, Noboru Kunihiro, Kazuo Ohta

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.

Quantum Information and Computation•May 1, 2007•37 citations

Reducing the Depth of Linear Reversible Quantum Circuits

Timothee Goubault de Brugiere, Marc Baboulin, Benoît Valiron +2 more

In quantum computing the decoherence time of the qubits determines the computation time available, and this time is very limited when using current hardware. In this article, we minimize the execution time (the depth) for a class of circuits referred to as linear reversible circuits, which has many applications in quantum computing (e.g., stabilizer circuits, “CNOT+T” circuits, etc.). We propose a practical formulation of a divide-and-conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms. We improve the theoretical upper bound of the depth in the worst case for some range of qubits. We also propose greedy algorithms based on cost minimization to find more optimal circuits for small or simple operators. Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.

arXiv:2201.06380•IEEE Transactions on Quantum Engineering•Jan 1, 2021•33 citations

Optimization and experimental realization of the quantum permutation algorithm

İ. Yalçınkaya, Z. Gedik

The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its $n$-qubit implementations, the number of required quantum gates scales quadratically with $n$ due to the quantum Fourier transforms included. We show here for the $n$-qubit case that the algorithm can be simplified so that it requires only $O(n)$ quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.

arXiv:1708.07900•Physical Review A•Dec 29, 2017•30 citations

Quantum algorithms: an overview

Ashley Montanaro

Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.

arXiv:1511.04206•npj Quantum Information•Jan 12, 2016•1,071 citations
In many candidate designs of solid-state quantum computers, interactions between qubits are limited to a small number of neighboring qubits. Taking into account this limitation we describe how quantum algorithms can be executed efficiently on these designs. We illustrate our results with the quantum Fourier transform for which linear depth networks are obtained. The concepts presented in this work can be applied to all quantum algorithms to reduce considerably the coherence time needed for their execution.
Recently, the quantum computer (QC) using the nano‐devices have significantly attracted attention, because a large‐scale extention of the qubits could be easily realized in the nano‐devices. However, some problems for the realization of the QC with nano‐devices arise from the short decoherence time and the interaction of qubits only between nearest‐neighbor qubits. Therefore, we try to design the optimal quantum circuit of the quantum Fourier transform in various network system by means of the genetic algorithm (GA).
Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation.
We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are O(n)O(n)O(n) and O(nlog⁡n)O(n\log n)O(nlogn), respectively, where nnn is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.
In quantum computing the decoherence time of the qubits determines the computation time available, and this time is very limited when using current hardware. In this article, we minimize the execution time (the depth) for a class of circuits referred to as linear reversible circuits, which has many applications in quantum computing (e.g., stabilizer circuits, “CNOT+T” circuits, etc.). We propose a practical formulation of a divide-and-conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms. We improve the theoretical upper bound of the depth in the worst case for some range of qubits. We also propose greedy algorithms based on cost minimization to find more optimal circuits for small or simple operators. Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.
The quantum permutation algorithm provides computational speed-up over classical algorithms for determining the parity of a given cyclic permutation. For its nnn-qubit implementations, the number of required quantum gates scales quadratically with nnn due to the quantum Fourier transforms included. We show here for the nnn-qubit case that the algorithm can be simplified so that it requires only O(n)O(n)O(n) quantum gates, which theoretically reduces the complexity of the implementation. To test our results experimentally, we utilize IBM's 5-qubit quantum processor to realize the algorithm by using the original and simplified recipes for the 2-qubit case. It turns out that the latter results in a significantly higher success probability which allows us to verify the algorithm more precisely than the previous experimental realizations. We also verify the algorithm for the first time for the 3-qubit case with a considerable success probability by taking the advantage of our simplified scheme.
Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.