Kolmogorov complexity of unitary transformations in quantum computing

• URL: http://arxiv.org/abs/2110.05937v6
• Date: Wed, 19 Jan 2022 04:52:00 GMT
• Title: Kolmogorov complexity of unitary transformations in quantum computing
• Authors: Alexei Kaltchenko
• Abstract summary: Kolmogorov complexity of unitary transformation is built upon Kolmogorov "qubit complexity" of Berthiaume, W. Van Dam and S. Laplante. 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Generalization of Modular Spread Complexity for Non-Hermitian Density Matrices [0.0]
  In this work we generalize the concept of modular spread complexity to the cases where the reduced density matrix is non-Hermitian. We define the quantity pseudo-capacity which generalizes capacity of entanglement, and corresponds to the early modular-time measure of pseudo-modular complexity. We show some analytical calculations for 2-level systems and 4-qubit models and then do numerical investigations on the quantum phase transition of transverse field Ising model.
  arXiv  Detail & Related papers  (2024-10-07T17:59:16Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Inducing Systematicity in Transformers by Attending to Structurally Quantized Embeddings [60.698130703909804]
  Transformers generalize to novel compositions of structures and entities after being trained on a complex dataset. We propose SQ-Transformer that explicitly encourages systematicity in the embeddings and attention layers. We show that SQ-Transformer achieves stronger compositional generalization than the vanilla Transformer on multiple low-complexity semantic parsing and machine translation datasets.
  arXiv  Detail & Related papers  (2024-02-09T15:53:15Z)
• Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• Chaos and multifold complexity for an inverted harmonic oscillator [0.0]
  We prove that complexity is dominated by the longest permutation of the given time combination in an alternating zig-zag'' order. We conjecture that the general structure for multifold complexity should hold true universally for generic quantum systems.
  arXiv  Detail & Related papers  (2022-11-06T14:19:48Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Forster Decomposition and Learning Halfspaces with Noise [60.691817861402676]
  A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. We show that any distribution can be decomposed efficiently as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently.
  arXiv  Detail & Related papers  (2021-07-12T17:00:59Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Aspects of The First Law of Complexity [0.0]
  We investigate the first law of complexity proposed in arXiv:1903.04511, i.e., the variation of complexity when the target state is perturbed. Based on Nielsen's geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit.
  arXiv  Detail & Related papers  (2020-02-13T21:15:57Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.