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:2109.01960

Classical Complexity of Unitary Transformations

Alexei Kaltchenko

Published Sep 5, 2021• 0 citations
arXivHTMLPDF

Abstract

We discuss a classical complexity of finite-dimensional unitary transformations, which can been seen as a computable approximation of classical descriptional complexity of a unitary transformation acting on a set of qubits.
DOI
10.48550/arxiv.2109.01960

Related papers

Descriptional complexity of unitary transformations

Alexei Kaltchenko

Weintroduce the notion of descriptional complexity of nite-dimensional unitary transformations, which is closely related to the notion of Kolmogorov complexity of a quantum state. In quantum computing, quantum states are associated with quantum data, and unitary transformations of quantum states are associated with quantum computer programs.

International Conference on Micro- and Nano-Electronics (ICMNE)•Jan 31, 2022•0 citations

On Kolmogorov Complexity of Unitary Transformations in Quantum Computing

Alexei Kaltchenko

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.

i-manager’s Journal on Mathematics•Jan 1, 2022•0 citations

Kolmogorov complexity of unitary transformations in quantum computing

Alexei Kaltchenko

We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.

arXiv:2110.05937•Oct 10, 2021•1 citation

Computational Complexity in the Analysis of Quantum Operations

Miosz Michalski

Mathematical theory of infinite dimensional Hilbert spaces and the theory of operator algebras acting in such spaces (or C algebras in a more abstract approach) provide a standard setting for the formulation of modern quantum mechanics. On the other hand, experimental and theoretical progress achieved in the field of quantum information theory in the last two decades has indicated the practical and technological importance of low-dimensional quantum systems, where only a few basic modes play a significant role. Such modes can often be effectively decoupled from the rest of the system and controlled separately, providing physical realizations of qubits, qutrits and other basic information carriers. Regardless of concrete physical realization, be it photon polarization, electron or nuclear spin, charge in Josephson junctions to name just a few, the mathematical description of such systems requires only finite-dimensional Hilbert space language and finite-dimensional matrix algebras. Such structures are in principle computationally manageable in sharp contrast to the infinite dimensional ones.

InTech eBooks•Jul 24, 2013•3 citations

How smooth is quantum complexity?

Vir B. Bulchandani, S. L. Sondhi

Abstract The “quantum complexity” of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational complexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators. One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.

arXiv:2106.08324•Journal of High Energy Physics•Oct 1, 2021•20 citations

Creating subgroups of U(2w) for quantum-minus computers

Alexis De Vos, Michiel Boes

Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.

Journal of Physics Conference Series•Mar 1, 2011•1 citation
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to unnormalized density operators, which are subsequently "purified" into unnormalized vectors in Hilbert space. We discuss the optimality of our notion of Kolmogorov complexity in a broad sense.
We introduce a notion of Kolmogorov complexity of unitary transformation, which can (roughly) be understood as the least possible amount of information required to fully describe and reconstruct a given finite unitary transformation. In the context of quantum computing, it corresponds to the least possible amount of data to define and describe a quantum circuit or quantum computer program. Our Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante via mapping from unitary transformations to positive operators, which are subsequently "purified". We discuss the optimality of our notion of Kolmogorov complexity in a broad sense and obtain a simple complexity bound.
Mathematical theory of infinite dimensional Hilbert spaces and the theory of operator algebras acting in such spaces (or C algebras in a more abstract approach) provide a standard setting for the formulation of modern quantum mechanics. On the other hand, experimental and theoretical progress achieved in the field of quantum information theory in the last two decades has indicated the practical and technological importance of low-dimensional quantum systems, where only a few basic modes play a significant role. Such modes can often be effectively decoupled from the rest of the system and controlled separately, providing physical realizations of qubits, qutrits and other basic information carriers. Regardless of concrete physical realization, be it photon polarization, electron or nuclear spin, charge in Josephson junctions to name just a few, the mathematical description of such systems requires only finite-dimensional Hilbert space language and finite-dimensional matrix algebras. Such structures are in principle computationally manageable in sharp contrast to the infinite dimensional ones.
Abstract The “quantum complexity” of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates. While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational complexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy. In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators. One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.
Classical reversible computers on w bits are isomorphic to the (finite) symmetric group S 2 w ; quantum computers on w qubits are isomorphic to the (Lie) unitary group U(2 w ). We investigate and classify groups X which represent computers intermediate between classical reversible computers and quantum computers. Such intermediate groups X may exist in three flavours: finite groups of order larger than (2 w )!, infinite but discrete groups, and Lie groups of dimension smaller than (2 w ). For our purpose, we start from 1-qubit transformations, represented by 2 × 2 unitary matrices. We call this group the creator. Its members are called gates and act on one qubit. Controlled gates are quantum circuits acting on w qubits, such that the 1-qubit transformation (applied to a particular qubit) depends on the state of the w − 1 other qubits. The controlled gates generate the group X of 2 w × 2 w matrices, called the creation. We discuss all creators of order up to 8. Additionally a creator of order 16 and one of order 192 are discussed.