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

arXiv:1405.5205 · Lecture notes in computer science

Quantum Circuits for the Unitary Permutation Problem

Stefano Facchini, Simon Perdrix

Published Jan 1, 2015• 28 citations
arXivHTMLPDF
DOI
10.1007/978-3-319-17142-5_28

Related papers

Constructing Quantum Circuits for Unitary Operations

Joanna Wiśniewska

•Jan 1, 2011•0 citations

Quantum and Classical Dynamics with Random Permutation Circuits

Bruno Bertini, Katja Klobas, Pavel Kos +1 more

Understanding thermalization in quantum many-body systems is among the most enduring problems in modern physics. A particularly interesting question concerns the role played by quantum mechanics in this process, i.e., whether thermalization in quantum many-body systems is fundamentally different from that in classical many-body systems and, if so, which of its features are genuinely quantum. Here, we study this question in minimally structured many-body systems that are only constrained to have local interactions, i.e., local random circuits. In particular, we introduce random permutation circuits (RPCs), which are circuits comprising gates that locally permute basis states, as a counterpart to random unitary circuits (RUCs), a standard toy model for generic quantum dynamics. RPCs represent a model for generic microscopic classical reversible dynamics but, interestingly, can be interpreted both as classical or as quantum dynamics. We show that, upon averaging over all circuit realizations, RPCs permit the analytical computation of several key quantities such as out-of-time-order correlators (OTOCs) and entanglement entropies. In the classical setting, we obtain similar exact results relating (quantum) purity to (classical) growth of mutual information and (quantum) OTOCs to (classical) decorrelators. We, thus, discover a series of exact relations, connecting quantities in RUC and (quantum or classical) RPCs. Our results indicate that, despite the fundamental differences between quantum and classical systems, their many-body dynamics exhibits remarkably similar behaviors.

arXiv:2407.11960•Physical Review X•Jan 28, 2025•14 citations

New Permutation-Free Quantum Circuits for Implementing 3- and 4-Qubit Unitary Operations

Artyom M. Grigoryan

The article presents the quantum signal-induced heap transform (QsiHT) method of the QR-decomposition of multi-qubit operations. This transform can be generated by a given signal, by using different paths, or orders, of processing the data. We propose using the concept of the fast path of calculation of the QsiHT and applying such transforms on each stage of the matrix decomposition. This allows us to build quantum circuits for multi-qubit unitary operation without permutations. Unitary operations with real and complex matrices are considered. The cases of 3- and 4-qubit operations are described in detail with quantum circuits. These circuits use a maximum of 28 and 120 Givens rotation gates for 3- and 4-qubit real operations, respectively. All rotations are performing only on adjacent bit planes. For complex unitary operation, each of the Givens gates is used in pairs with two Z-rotation gates. These two types of rotations and the global phase gate are the universal gate set for multi-qubit operations. The presented approach can be used for implementing quantum circuits for n-qubits when n≥2, with a maximum of (4n/2−2n−1) Givens rotations and no permutations.

Information•Jul 21, 2025•5 citations

Quantum Circuits and Computation

François Chapeau‐Blondeau

Springer eBooks•Jan 1, 2026•0 citations

On the Hardness of Approximate Quantum Circuit Membership and Optimization

Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

quant-pharXiv:2611.04381•Nov 4, 2026•0 citations

Quantum Combinational Circuits

Hafiz Md. Hasan Babu

Springer eBooks•Jan 1, 2025•0 citations
Understanding thermalization in quantum many-body systems is among the most enduring problems in modern physics. A particularly interesting question concerns the role played by quantum mechanics in this process, i.e., whether thermalization in quantum many-body systems is fundamentally different from that in classical many-body systems and, if so, which of its features are genuinely quantum. Here, we study this question in minimally structured many-body systems that are only constrained to have local interactions, i.e., local random circuits. In particular, we introduce random permutation circuits (RPCs), which are circuits comprising gates that locally permute basis states, as a counterpart to random unitary circuits (RUCs), a standard toy model for generic quantum dynamics. RPCs represent a model for generic microscopic classical reversible dynamics but, interestingly, can be interpreted both as classical or as quantum dynamics. We show that, upon averaging over all circuit realizations, RPCs permit the analytical computation of several key quantities such as out-of-time-order correlators (OTOCs) and entanglement entropies. In the classical setting, we obtain similar exact results relating (quantum) purity to (classical) growth of mutual information and (quantum) OTOCs to (classical) decorrelators. We, thus, discover a series of exact relations, connecting quantities in RUC and (quantum or classical) RPCs. Our results indicate that, despite the fundamental differences between quantum and classical systems, their many-body dynamics exhibits remarkably similar behaviors.
The article presents the quantum signal-induced heap transform (QsiHT) method of the QR-decomposition of multi-qubit operations. This transform can be generated by a given signal, by using different paths, or orders, of processing the data. We propose using the concept of the fast path of calculation of the QsiHT and applying such transforms on each stage of the matrix decomposition. This allows us to build quantum circuits for multi-qubit unitary operation without permutations. Unitary operations with real and complex matrices are considered. The cases of 3- and 4-qubit operations are described in detail with quantum circuits. These circuits use a maximum of 28 and 120 Givens rotation gates for 3- and 4-qubit real operations, respectively. All rotations are performing only on adjacent bit planes. For complex unitary operation, each of the Givens gates is used in pairs with two Z-rotation gates. These two types of rotations and the global phase gate are the universal gate set for multi-qubit operations. The presented approach can be used for implementing quantum circuits for n-qubits when n≥2, with a maximum of (4n/2−2n−1) Givens rotations and no permutations.
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries SSS, decide whether a given circuit CCC is within distance ε\varepsilonε of a unitary in SSS under some metric mmm. Membership is a special case of optimization, where SSS is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case S={I}S=\{I\}S={I} (approximate identity) is QMA-complete when CCC is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides S={I}S=\{I\}S={I}, sets SSS containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of ε\varepsilonε, provided CCC's gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If S={I}S=\{I\}S={I}, or if SSS contains only generalized permutation matrices, I∈SI\in SI∈S, and mmm is a trace-based distance, PP-hardness holds for all non-trivial ε\varepsilonε. If S={I}S=\{I\}S={I} and mmm is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.