Algorithmic complexity of the universe and quantum transitions splitting off extra coordinates

We consider a model of quantum gravitation in which the probability of the appearance of any quantum gravitational objects is connected with their Kolmogorov algorithmic complexity. We show that in such a case, extra coordinates may be split off.Kyrgyz State University. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Fizika, No. 9, pp. 55–59, September, 1994.     

Algorithmic complexity of a Schwartzschild black hole

The Kolmogorov algorithmic complexity of a Schwartzschild black hole is calculated with the application of concepts of information theory. In the calculation of the trajectory integral in the quantum theory of gravitation, the action function is replaced by the algorithmic complexity function.Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Fizika, No. 3, pp. 108–111, March, 1995.     

Algorithmic treatment of the spin-echo effect

We analyze the apparent increase in entropy in the course of the spin-echo effect using algorithmic information theory. We show that although the state of the spins quickly becomes algorithmically complex, then simple again during the echo, the overall complexity of spins together with the magnetic field grows slowly, as the logarithm of the elapsed time. This slow increase in complexity is reflected in an increased difficulty in taking advantage of the echo pulse. Our discussion illustrates the fundamental role of algorithmic information content in the formulation of statistical physics, including the second law of thermodynamics, from the viewpoint of the observer.     

Quantum knitting

We analyze the connections between the mathematical theory of knots and quantum physics by addressing a number of algorithmic questions related to both knots and braid groups. Knots can be distinguished by means of “knot invariants,” among which the Jones polynomial plays a prominent role, since it can be associated with observables in topological quantum field theory. Although the problem of computing the Jones polynomial is intractable in the framework of classical complexity theory, it has been recently recognized that a quantum computer is capable of approximating it in an efficient way. The quantum algorithms discussed here represent a breakthrough for quantum computation, since approximating the Jones polynomial is actually a “universal problem,” namely, the hardest problem that a quantum computer can efficiently handle.     

Symmetric extensions of quantum States and local hidden variable theories

While all bipartite pure entangled states violate some Bell inequality, the relationship between entanglement and nonlocality for mixed quantum states is not well understood. We introduce a simple and efficient algorithmic approach for the problem of constructing local hidden variable theories for quantum states. The method is based on constructing a so-called symmetric quasiextension of the quantum state that gives rise to a local hidden variable model with a certain number of settings for the observers Alice and Bob.     

Quantum communication complexity protocol with two entangled qutrits

We formulate a two-party communication complexity problem and present its quantum solution that exploits the entanglement between two qutrits. We prove that for a broad class of protocols the entangled state can enhance the efficiency of solving the problem in the quantum protocol over any classical one if and only if the state violates Bell's inequality for two qutrits.     

Bidirectional Information Flow Quantum State Tomography

The exact reconstruction of many-body quantum systems is one of the major challenges in modern physics,because it is impractical to overcome the exponential complexity problem brought by high-dimensional quantum manybody systems.Recently,machine learning techniques are well used to promote quantum information research and quantum state tomography has also been developed by neural network generative models.We propose a quantum state tomography method,which is based on a bidirectional gated recurrent unit neural network,to learn and reconstruct both easy quantum states and hard quantum states in this study.We are able to use fewer measurement samples in our method to reconstruct these quantum states and to obtain high fidelity.     

Computational difficulty of computing the density of states

We study the computational difficulty of computing the ground state degeneracy and the density of states for local Hamiltonians. We show that the difficulty of both problems is exactly captured by a class which we call #BQP, which is the counting version of the quantum complexity class quantum Merlin Arthur. We show that #BQP is not harder than its classical counting counterpart #P, which in turn implies that computing the ground state degeneracy or the density of states for classical Hamiltonians is just as hard as it is for quantum Hamiltonians.     

Quantum light storage in rare-earth-ion-doped solids

The reversible transfer of unknown quantum states between light and matter is essential for constructing large-scale quantum networks. Over the last decade, various physical systems have been proposed to realize such quantum memory for light. The solid-state quantum memory based on rare-earth-ion-doped solids has the advantages of a reduced setup complexity and high robustness for scalable application. We describe the methods used to spectrally prepare the quantum memory and release the photonic excitation on-demand. We will review the state of the art experiments and discuss the perspective applications of this particular system in both quantum information science and fundamental tests of quantum physics.     

The Sign and Micro-Origin of Complexity as Entropy (Conjectured Resolution of a Paradox)

Evolution produces ever more ordered matter, while also increasing its complexity all the time. There are various ways of measuring complexity, such as Kolmogorov's algorithmic complexity, drawn from information theory, and identified with entropy, enchancing irreversibility in harmony with the second law of thermodynamics. On the other hand, however, the creation of order should have reduced entropy; quoting Schroedinger, it represents "negentropy." To resolve this apparent contradiction we first review a similar set up (though with a totally different interaction) occurring in black holes, a model in which the physics are now explicit and fully understood at the quantum level.     

Condition for any realistic theory of quantum systems

In quantum physics, the density operator completely describes the state. Instead, in classical physics the mean value of physical quantities is evaluated by means of a probability distribution. We study the possibility to describe pure quantum states and events with classical probability distributions and conditional probabilities and prove that the distributions have to be nonlinear functions of the density operator. Some examples are considered. Finally, we deal with the exponential complexity problem of quantum physics and introduce the concept of classical dimension for a quantum system.     

A generalized tripartite scheme for splitting an arbitrary 2-qubit state with three 2-qubit partially entangled states and the Kraus measurement

We put forward a generalized tripartite scheme for splitting an arbitrary 2-qubit pure state with three 2-qubit non-maximally en-tangled states as quantum channels.The scheme for the first time incorporates the Kraus measurement into quantum information splitting scheme.In contrast to the similar scheme using the same quantum channels and the ancilla-entangled measurement,our scheme is superior in terms of operation and complexity,success probability,resource consumption and effciency.     

The decrease in the overall algorithmic complexity of the spin-echo effect

Recently Lloyd and Zurek studied the algorithmic complexity of the spin-echo effect and concluded that the overall complexity of spins together with the magnetic field grew slowly even during the rephasing stage. In this paper we show that, in contrast to their conclusion, the complexity decreases during the rephasing stage. We also clarify the origin of the disagreement.     

Conditions for quantum violation of macroscopic realism

Why do we not experience a violation of macroscopic realism in everyday life. Normally, no violation can be seen either because of decoherence or the restriction of coarse-grained measurements, transforming the time evolution of any quantum state into a classical time evolution of a statistical mixture. We find the sufficient condition for these classical evolutions for spin systems under coarse-grained measurements. However, there exist "nonclassical" Hamiltonians whose time evolution cannot be understood classically, although at every instant of time the quantum state appears as a classical mixture. We suggest that such Hamiltonians are unlikely to be realized in nature because of their high computational complexity.     

All-silicon quantum computer

A solid-state implementation of a quantum computer composed entirely of silicon is proposed. Qubits are 29Si nuclear spins arranged as chains in a 28Si (spin-0) matrix with Larmor frequencies separated by a large magnetic field gradient. No impurity dopants or electrical contacts are needed. Initialization is accomplished by optical pumping, algorithmic cooling, and pseudo-pure state techniques. Magnetic resonance force microscopy is used for ensemble measurement.     

Quantum Adder for Superposition States

Quantum superposition is one of the essential features that make quantum computation surpass classical computation in space complexity and time complexity. However, it is a double-edged sword. For example, it is troublesome to add all the numbers stored in a superposition state. The usual solution is taking out and adding the numbers one by one. If there are \(2^{n}\) numbers, the complexity of this scheme is \(O(2^{n})\) which is the same as the complexity of the classical scheme \(O(2^{n})\). Moreover, taking account to the current physical computing speed, quantum computers will have no advantage. In order to solve this problem, a new method for summing all numbers in a quantum superposition state is proposed in this paper, whose main idea is that circularly shifting the superposition state and summing the new one with the original superposition state. Our scheme can effectively reduce the time complexity to \(O(n)\).     

Spin based heat engine: demonstration of multiple rounds of algorithmic cooling

We experimentally demonstrate multiple rounds of heat-bath algorithmic cooling in a 3 qubit solid-state nuclear magnetic resonance quantum information processor. By pumping entropy into a heat bath, we are able to surpass the closed system limit of the Shannon bound and purify a single qubit to 1.69 times the heat-bath polarization. The algorithm combines both high fidelity coherent control and a deliberate interaction with the environment. Given this level of quantum control in systems with larger reset polarizations, nearly pure qubits should be achievable.     

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.