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
S, decide whether a given circuit
C is within distance
ε 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
ε, 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∈S, and
m is a trace-based distance, PP-hardness holds for all non-trivial
ε. 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.