This note considers Kak's observer-reference model of quantum information, where it is shown that qubits carry information that is sqrt n / ln n times classical information, where n is the number of components in the measurement system, to analyze information processing in quantum gates. The obverse side of this exponential nature of quantum information is that the computational complexity of implementing unconditionally reliable quantum gates is also exponential.
This note considers Kak's observer-reference model of quantum information, where it is shown that qubits carry information that is sqrt n / ln n times classical information, where n is the number of components in the measurement system, to analyze information processing in quantum gates. The obverse side of this exponential nature of quantum information is that the computational complexity of implementing unconditionally reliable quantum gates is also exponential.
In quantum mechanics, a state is an element of a Hilbert space whose dimension exponentially grows with the increase of the number of particles (or qubits, in quantum computing). The vague question "is this huge Hilbert space really there?" has been rigorously formalized inside the computational complexity theory; the research suggests a positive answer to the question. Along this line, I give a definition of the (classical) information content of a quantum state, taking inspiration from the Kolmogorov complexity. I show that, for some well-known quantum circuits (having a number of gates polynomial in the number of qubits), the information content of the output state, evaluated according to my definition, is polynomial in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states, having an exponentially-growing information content. A huge amount of classical information can be really present inside a quantum state, however, I show that this property is not necessarily exploited by quantum computers, not even by quantum algorithms showing an exponential speed-up with respect to classical computation.
The description of the state of an n-bit quantum system requires 2n-1 complex numbers. This exponentially large information capacity of quantum states has been exploited in recent results showing both exponential speed-up, and exponential savings in communication costs in solving certain problems using quantum computers. In this dissertation, we establish limitations on the ways in which the exponentially many degrees of freedom hidden in quantum states may be accessed. More specifically, we give tight bounds for random access codes, which allow us to encode classical information using quantum bits such that only a small portion of the encoded information may be recovered via a measurement. This also sheds light on the power of computing with a finite number of quantum bits—using these techniques, we show an exponential size lower bound for quantum finite automata for a problem which can be solved on a linear size classical automaton. We then consider the complexity of solving certain problems in the quantum black-box model, an information theoretic model that has been a rich source of insights into the nature of quantum computation. We derive nearly optimal lower bounds for several problems in this model, including that of approximating the median. We also give new, optimal algorithms for approximate medians and other order statistics.
In general, all forms of information processing can be considered in a quantum mechanical context, including for example communication, channel capacities, and the quantum limits to information extraction. In this chapter we introduce the basic features of quantum information processing. We first present qubits as abstractions of two-level addressable quantum systems, before generalizing this concept to higher-dimensional qudit systems, and continuous variables. We introduce the stabilizer formalism towards the beginning of our discussion as a convenient way to track quantum information. In Section 2.2 we derive the no-cloning theorem, which leads us to cryptography, teleportation, and quantum repeaters. Section 2.3 describes quantum computing with qubits. We start with a brief description of the circuit model, and use it to define cluster states and the one-way model. We study the properties of cluster states and discuss error correction. In the last section we introduce quantum computing over continuous variables. Quantum information Classically, information is carried by ‘bits’, which are physical systems that have two (macroscopic) states denoted by 0 and 1. These bits are described classically, which immediately raises the question of how we should extend this information-theoretic description to the quantum mechanical case. This will lead to the quantum unit of information, the quantum bit or ‘qubit’. 2.1.1 Classical and quantum bits We can define the qubit as a two-dimensional quantum system, which means that the state space of the system is a two-dimensional complex Hilbert space ℋ.
Quantum memory systems are vital in quantum information processing for dependable storage and retrieval of quantum states. Inspired by classical reliability theories that synthesize reliable computing systems from unreliable components, we formalize the problem of reliable storage of quantum information using noisy components. We introduce the notion of stable quantum memories and define the storage rate as the ratio of the number of logical qubits to the total number of physical qubits as well as the circuit complexity of the decoder, which includes both quantum gates and measurements. We demonstrate that a strictly positive storage rate can be achieved by constructing a quantum memory system with quantum expander codes. Moreover, by reducing the reliable storage problem to reliable quantum communication, we provide upper bounds on the achievable storage capacity. In the case of physical qubits corrupted by noise satisfying hypercontractivity conditions, we provide a tighter upper bound on storage capacity using an entropy dissipation argument. Furthermore, observing that the time complexity of the decoder scales nontrivially with the number of physical qubits, achieving asymptotic rates may not be possible due to the induced dependence of the noise on the number of physical qubits. In this constrained nonasymptotic setting, we derive upper bounds on storage capacity using finite blocklength communication bounds. Finally, we numerically analyze the gap between upper and lower bounds in both asymptotic and nonasymptotic cases, and provide suggestions to tighten the gap.
Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process’s complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n -qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state in our model, via a complexity-constrained process, is quantified by the state’s . The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the . The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer’s ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy. In a random circuit—a simple model for quantum chaotic dynamics—the complexity entropy transitions from zero to its maximal value around the time corresponding to the observer’s computational-power limit. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a , which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of , as quantified by .
Quantum computation has shown a lot of promise in being able to provide computational results not possible with the modern computer. However, the design of new algorithms has been slow. One reason for this could be that we simply do not understand this new paradigm of computation enough to fully utilize it. We present here is an improvement of our previous generalization the basic quantum gates and a new perspective on quantum computation and quantum information. The goal is to obtain a more abstract approach to quantum computation and quantum algorithms in which physical systems are viewed as the implementation for the computing paradigm and not the reason for the it