For pure three-qubit states the classification of entanglement is both non-trivial and well understood. In this work, we study the quantum algorithmic complexity introduced in [1] of three-qubit pure states belonging to the most general class of entanglement. Contrary to expectations we find out that the degree of entanglement of states in this class quantified by the measure of 3-tangle, does not correlate with the quantum algorithmic complexity, defined as the length of the shortest circuit needed to prepare the state. For a given entangled state the evaluation of its quantum complexity is done via a pseudo random evolutionary algorithm. This algorithm allows us not only to determine the complexity of a quantum circuit in terms of the number of required quantum gates, but also to estimate another type of complexity related to the time required to obtain the correct answer.
For pure three-qubit states the classification of entanglement is both non-trivial and well understood. In this work, we study the quantum algorithmic complexity introduced in [1] of three-qubit pure states belonging to the most general class of entanglement. Contrary to expectations we find out that the degree of entanglement of states in this class quantified by the measure of 3-tangle, does not correlate with the quantum algorithmic complexity, defined as the length of the shortest circuit needed to prepare the state. For a given entangled state the evaluation of its quantum complexity is done via a pseudo random evolutionary algorithm. This algorithm allows us not only to determine the complexity of a quantum circuit in terms of the number of required quantum gates, but also to estimate another type of complexity related to the time required to obtain the correct answer.
We present a deterministic framework for preparing an arbitrary three-qubit pure state. To leverage entanglement structure in the state-preparation task, we classify three-qubit pure states into five types with respect to a 1∣2 bipartition. Given a target state specified by its amplitudes, we provide concrete criteria and concurrence-based tests that determine its type. For each type, we derive an explicit circuit template composed of elementary single-qubit rotations and CNOT gates, with gate parameters determined systematically from the Schmidt decomposition. The full construction is described step by step from the target amplitudes, with no procedural ambiguity. As an application, we further group frequently encountered three-qubit pure states in quantum information into four classes and provide an explicit circuit for each class. Compared with prior approaches, our circuits are designed for practical use: they admit a direct algorithmic instantiation, use only CNOT gates between adjacent qubits, and for certain classes achieve smaller gate counts and circuit depth.
Abstract The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. The creation complexity of quantum states is closely related to the complexity of quantum circuits, which is crucial in developing efficient quantum algorithms that can outperform classical algorithms. A major question unanswered so far is what quantum states can be created with a number of elementary gates that scales polynomially with the number of qubits. In this work, it is first shown that for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is polynomial. Then, it is shown that it is possible for a large class of quantum states with polynomial creation complexity to have common coefficient features such that, given any candidate quantum state, an efficient coefficient sampling procedure can be designed to determine if the state belongs to the class or not with arbitrarily high success probability. Consequently, partial knowledge of a quantum state's creation complexity is obtained, which can be useful for designing quantum circuits and algorithms involving such a state.
This paper explores the application of information theory to analyze the computational complexity of quantum algorithms. Traditional approaches to complexity analysis often rely on circuit models and gate complexity, which can be insufficient for fully characterizing the resource requirements of quantum computation. We propose utilizing information-theoretic concepts, specifically quantum entropy and mutual information, to provide a more nuanced understanding of how quantum circuits process information. This approach allows us to quantify the information-theoretic limits of quantum algorithms, providing insights into the number of qubits and gates necessary for efficient execution. We examine several key aspects, including the role of entanglement, the impact of measurement, and the relationship between quantum entropy and algorithmic complexity. The goal is to establish a framework for assessing quantum algorithms based on their fundamental information-processing capabilities, moving beyond purely circuit-based evaluations. This work contributes to a deeper theoretical understanding of quantum computation and its potential limitations.
Entanglement is an important resource for quantum technologies that allow us to go beyond the classical world. Quantum systems can be entangled in various ways. Also, the degree of entanglement between the subsystems of a quantum system can be calculated in different ways. In our recent paper [Prog. Theor. Exp. Phys. (2022)], we directly measure the three-tangle of a pure three-qubit quantum state. In this paper, we extend this method to pure N-qubit quantum states (N is any odd number greater than 1) by considering polynomial invariant of degree 4 as a measure of entanglement. In this algorithm, we use quantum gates and output probabilities to calculate polynomial invariant of degree 4. The importance of this method lies in the possibility of experimental implementation of quantum calculations in the language of quantum gates.
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.
Entanglement is a physical phenomenon that links a pair, or a set of particles that correlates with each other, regardless of the distance between them. Recent researches conducted on entanglement are mostly focused on measurement and classification in multiqubit systems. Classification of two qubits will only distinguish the quantum state as either separable or entangled, and it can be done by measurement. Meanwhile, in a three-qubit system, it becomes more complex because of the structure of the three qubits itself. It is not sufficient to do measurement because the states are divided into three types, including fully separable state, biseparable state, and genuine entangled state. Therefore, the classification is needed to distinguish the type of states in the three-qubit system. This study aims to classify the entanglement of three-qubit pure states using a combination model of special unitary groups, SU(2) and SU(4), by changing the angle of selected parameters in SU(4) and acting on the separable pure state. The matrix represents SU(2) is 2×2 matrix while matrix for SU(4) is 4×4 matrix. Hence, the combination of SU(2) and SU(4) represent 8×8 matrix. This classification uses the von Neumann entropy and three tangle measurements to classify the class, respectively. The results of this study have indicated that the three-qubit pure state has been successfully classified into different classes, namely, A-B-C, A-BC, C-AB, GHZ, and W, with A-B-C being a fully separable state, A-BC and C-AB are biseparable states, and GHZ and W are genuine entangled states. The results show that this model can change separable pure states to other entanglement class after transformation is done.