{'fraction_non_alphanumeric': 0.03645686594917451, 'fraction_numerical': 0.007099791514058714, 'mean_word_length': 4.301075268817204, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum Kolmogorov Complexity and Bounded Quantum Memory

In this study, the effect of bounded quantum memory in a primitive information protocol has been examined using the quantum Kolmogorov complexity as a measure of information. We employed a toy two-party protocol in which Bob by using a bounded quantum memory and an unbounded classical memory estimates a message that was encoded in qubits by Alice in one of the bases X or Z. Our theorem gave a nontrivial effect of the memory boundedness. In addition, a generalization of the uncertainty principle in the presence of quantum memory has been obtained.


I. INTRODUCTION
Various ideas have been put forth and experiments have been conducted to construct a large and stable quantum memory. This is definitely the most important factor for achieving quantum information processing devices. However, despite the efforts expended thus far, it is difficult to imagine that any ultimate method will be proposed that enables the construction of an arbitrarily large quantum memory.
This pessimistic view is not as disappointing as it may seem. Let us consider a two-party cryptographic protocol called oblivious transfer [1], in which Alice sends a bit to Bob by executing a protocol in such a manner that Bob receives it correctly with probability 1/2 and nothing otherwise, but Alice cannot learn whether her bit was received. While the oblivious transfer could be a strong cryptographic primitive when realized, its secure realization without considering any assumptions is impossible even if one uses quantum communication [2,3]. Several studies have been conducted to investigate physical assumptions yielding the secure implementation of this protocol using classical communication. The first assumption is the boundedness of computation power, which is the most traditional approach based on a mathematically unproven computational complexity problem [1]. This approach implicitly contains a physical assumption: it assumes the processing speed of existing computers. The second assumption involves the imperfection of a communication channel. It has been demonstrated in various noise models that secure oblivious transfer is achievable [4,5]. The third assumption, which is related to the present study, is the boundedness of memory size. It has been shown that the protocol may be securely implemented if the size of an adversary's (classical) memory is restricted [6]. Although this result is interesting in theory, the assumption is not entirely valid because it is not too difficult to construct large classical memories with current technology. Recently, important work based on bounded quantum memory has been completed. In [7], Damgaard et al. have shown that the oblivious transfer becomes information-theoretically secure under the assumption that the size of the adversary's quantum memory is bounded. As mentioned earlier, the assumption of bounded quantum memory is more reasonable than that of bounded classical memory. In fact, the latest technology enables the stability of only a few qubits of memory.
The protocol runs as follows. Alice encodes a random N bit sequence to a quantum state of N qubits in X or Z basis. She sends the qubits to Bob. Bob selects X or Z and measures the qubits with respect to the selected basis. After Alice announces the basis used for encoding, Bob knows whether his selection of the basis is correct. The privacy amplification phase causes the players to agree on a bit in the case that the basis is correct, otherwise the protocol makes Bob completely ignorant of the bit obtained by Alice. Alice can send Bob an arbitrary bit by XORing with her obtained bit. As intended, this method works as an oblivious channel. To demonstrate the security, assume that one of the players, Bob, is dishonest. If Bob has a quantum memory of size larger than N , he may not follow the protocol but may keep the quantum state and measure it with respect to the disclosed basis. This procedure provides the full information of an encoded sequence to Bob; thus the protocol fails. Further, imagine a case in which dishonest Bob's quantum memory is bounded. Since he cannot keep the entire quantum state, he has to irreversibly convert a part of the quantum state to the classical state by measuring a part of qubits. This operation destroys the quantum state and the information encoded in it. It is essential that he is unaware of the basis used for encoding when the qubits are passed to him. In view of the fact that the noncommutativity of X and Z prohibits their joint measurement, any measurement inevitably induces loss of information. For instance, suppose that Bob with M (< N ) qubits memory employs the following simple strategy. When the qubits are sent, Bob keeps the first M qubits as they are and measures the remaining N − M qubits in the Z basis. This strategy allows Bob to obtain full information if the basis used by Alice for encoding was Z. Conversely, it does not provide full information to Bob if the basis used by Alice was X, because he loses the information that was encoded in the first M qubits. Damgaard et al. [7] has shown that dishonest Bob must have at least N/2 qubits quantum memory to benefit in this protocol. That is, the protocol works under the assumption of bounded quantum memory of size smaller than N/2.
In this study, we inspect a toy two-party protocol that corresponds to the oblivious transfer protocol with dishonest Bob, but is not followed by privacy amplification. Consider the following problem. Assume that Alice encodes a random N bit sequence to a quantum state in the X or Z basis. How much information can Bob, who has a bounded quantum memory and an unbounded classical memory, retrieve after the basis is announced? By extracting part of a protocol in this manner, it is hoped that the understanding of the power of bounded quantum memory can be deepened. In addition, it may help improve the existing result, as was the case for the quantum key distribution protocol. We study the problem by employing the quantum Kolmogorov complexity as a measure of information, as defined by Vitányi [9]. In contrast to Shannon's theory, which treats only information of probabilistic sources, the Kolmogorov complexity is often called absolute information because it can assign information to individual objects.
The key notion is algorithmic randomness. The complexity of an object is defined as the shortest description length in both classical Kolmogorov complexity and quantum Kolmogorov complexity given by Vitányi. While the quantum Kolmogorov complexity is a natural concept for absolute information, it has been used in quantum information theory to develop only a few applications [10,11] developed in the quantum information theory. One of the purposes of this study is to demonstrate the usefulness of the quantum Kolmogorov complexity for analyzing protocols in this area.
The next section contains a brief review of the quantum Kolmogorov complexity as defined by Vitányi. In section III, we introduce a toy two-party protocol and describe our main result based on it. The conclusion contains a discussion of the results.

II. QUANTUM KOLMOGOROV COMPLEXITY BASED ON CLASSICAL DESCRIPTION
The classical Kolmogorov complexity of a binary sequence is defined by the length of the shortest program, as proposed by Kolmogorov [12] and Chaitin [13] independently, for a one-way Turing machine to output the sequence. For instance, a binary sequence "000 . . . 00" has a short description such as "print "0" 10000 times," which therefore has a small Kolmogorov complexity. If a binary sequence has no pattern that yields any compressed description, the best way to describe it is to write it down naively. Such a sequence is called random. That is, a binary sequence is random if and only if its Kolmogorov complexity is as large as its own length. Although a specification of a Turing machine is required to define its value, the Kolmogorov complexity does not depend on the choice of a Turing machine except for a trivial constant. Moreover, the classical Kolmogorov complexity and its conditional version have various rational properties, as do Shannon entropy and conditional entropy. The Kolmogorov complexity plays a central role in field of algorithmic information theory whose applications extend to vast areas such as the foundation of mathematics, computation theory, and physics [14,15].
While it seems natural to define the corresponding complexity for quantum states, the quantum versions [9,[16][17][18][19][20] of the Kolmogorov complexity were only recently proposed. Among the several versions of the quantum Kolmogorov complexity, we employ the one that was defined by Vitányi [9]. Vitányi's definition based on the classical description length is suitable for quantum information-theoretic problems that normally handle classical inputs and outputs. In order to explain the definition precisely, a description of a one-way quantum Turing machine is needed. A one-way quantum Turing machine consists of four tapes and an internal control. (See [9] for more details.) Each tape is a one-way infinite qubit (quantum bit) chain and has a corresponding head on it. One of the tapes works as the input tape and is read-only from left-to-right. A program is given on this tape as an initial condition. The second tape functions as the work tape. The work tape is initially set to be 0 for all the cells. The head on this tape can read and write a cell, and can move in both directions. The third tape is called an auxiliary tape. One can put an additional input on this tape. The additional input is written to the left-most qubits and can be a quantum state or a classical state. This input is needed when one deals with the conditional Kolmogorov complexity. The fourth tape works as the output tape. It is assumed that after halting the state over this tape will not be changed. The internal control is a quantum system described by a finite dimensional Hilbert space that has two special orthogonal vectors |q 0 (initial state) and |q f (halting state). After each step one makes a measurement of a coarse grained observable on the internal control {|q f q f |, 1 − |q f q f |} to know if the computation halts [21]. A computation halts at time t if and only if the probability to observe q f at time t is 1, and at any time t ′ < t the probability to observe q f is zero (see [22][23][24][25] for relevant discussions). By using this one-way quantum Turing machine, Vitányi defined the quantum Kolmogorov complexity as the length of the shortest description of a quantum state. That is, the programs of quantum Turing machine are restricted to classical ones, while the auxiliary inputs can be quantum states. We write U (p, y) = |x if and only if a quantum Turing machine U with a classical program p and an auxiliary (classical or quantum) input y halts and outputs |x . The following is the precise description of Vitányi's definition.
Definition 1 [9] The (self-delimiting) quantum Kolmogorov complexity of a pure state |x with respect to a one-way quantum Turing machine U with y (possibly a quantum state) as conditional input given for free is where l(p) is the length of a classical program p, and ⌈a⌉ is the smallest integer larger than a.
The one-wayness of the quantum Turing machine ensures that the halting programs compose a prefix free set. Because of this, the length l(p) is defined consistently. The term ⌈− log | z|x | 2 ⌉ represents how insufficiently an output |z approximates the desired output |x . This additional term has a natural interpretation using the Shannon-Fano code. Vitányi has shown the following invariance theorem, which is very important.
Theorem 1 [9] There is a universal quantum Turing machine U , such that for all machines Q, there is a constant c Q , such that for all quantum states |x and all auxiliary inputs y we have: Thus the value of quantum Kolmogorov complexity does not depend on the choice of a quantum Turing machine if one neglects the unimportant constant term c Q . Thanks to this theorem, one often writes K instead of K U . Moreover, the following theorem is crucial for our discussion.
Theorem 2 [9] On classical objects (that is, finite binary strings that are all directly computable) the quantum Kolmogorov complexity coincides up to a fixed additional constant with the self-delimiting Kolmogorov complexity. That is, there exists a constant c such that for any classical binary sequence |x , According to this theorem, for classical objects it essentially suffices to treat only programs that exactly output the object.

III. FORMULATION AND RESULTS
In order to discuss the power of the bounded quantum memory, we use a toy two-party protocol. Suppose that there exist two players Alice and Bob. Alice encodes a message in qubits with one of the bases X or Z, and sends them to Bob. The precise formulation is as follows. Alice chooses probabilistically [26] an N -bit message x ∈ {0, 1} N . She also chooses a basis X or Z for its encoding. We write the standard basis of a qubit as {|0 , |1 }, which are eigenstates of Z. Its conjugate basis is written as {|0 , |1 }, which are eigenstates of X and are defined as |0 := 1 √ 2 (|0 + |1 ) and |1 := 1 √ 2 (|0 − |1 ). She prepares a quantum state of N qubits described by a Hilbert space H A as follows. If her choice of basis is X, she encodes her message x = x 1 x 2 · · · x N ∈ {0, 1} N as |x := |x 1 ⊗ |x 2 ⊗ · · · ⊗ |x N ∈ H A . Conversely, if her choice of basis is Z, she prepares |x := |x 1 ⊗ |x 2 ⊗ · · · ⊗ |x N ∈ H A . We define X x := |x x| for each x ∈ {0, 1} N and Z z := |z z| for each z ∈ {0, 1} N . Bob, who has a bounded quantum memory and an unbounded classical memory, tries estimating the message after the basis is disclosed by Alice. There may exist some different formulations of the quantum bounded memory. For instance, one of the possible definitions would be such that Bob has many qubits that decohere in an uncontrollable way except for some M qubits. On the other hand, the following definition employed in this paper gives Bob the ability to control the system. Bob has an arbitrarily large system and he makes it interact with the qubits sent from Alice. The whole system that Bob possesses after the interaction is divided into two parts as H m ⊗ K. The first part is the quantum memory that consists of M qubits. The second part is called an auxiliary part whose size can be arbitrarily large. Because Bob cannot keep the quantum coherence of the auxiliary part, he makes a measurement of an observable on it before the basis is announced by Alice. Let us denote the observable by C = {C ξ }, which forms a positive-operator-valued measure (POVM) on K. The measurement result is stored in a classical memory whose size can be arbitrarily large. For as long as he needs, Bob can keep the quantum state on the quantum memory. He estimates the message encoded by Alice by using the quantum state in the quantum memory, the classical data in the classical memory and the basis disclosed by Alice. The whole process can be written as follows. The interaction between the qubits sent by Alice and Bob's apparatus is described by a completely positive map (CP-map), where Σ(H) denotes a set of all density operators on H. For instance, if Alice uses the basis Z for encoding message z, the state after the interaction becomes Λ(|z z|). Suppose that Bob obtained ξ as an outcome. The quantum state kept in the quantum memory depends on Z, z, and ξ, and is denoted by ρ Z z,ξ ∈ Σ(H m ), which can be calculated as an a-posteriori state [27]. We treat the quantum Kolmogorov complexity K(z|ρ Z z,ξ , ξ, Z) as a measure to characterize Bob's estimation [28]. That is, if Bob can estimate z exactly only from what he actually has, K(z|ρ Z z,ξ , ξ, Z) = O(1) holds. Otherwise, the quantum Kolmogorov complexity becomes nontrivial. Similarly, when Alice uses the basis X for encoding message x, and Bob obtains ξ as an outcome of the measurement on the auxiliary system, we denote the quantum state in the quantum memory by ρ X x,ξ ∈ Σ(H m ). K(x|ρ X x,ξ , ξ, X) characterizes Bob's ability to estimate the message x [28].
When M ≥ N holds, Bob can recover the message perfectly by simply keeping the quantum states sent by Alice. We study how well Bob can recover the message when M < N is satisfied.
In the following theorem, we study asymptotic behavior with respect to increasing N . For each N , the size of Bob's quantum memory M , which may depend on N , is bounded as M ≤ qN for some q (0 ≤ q ≤ 1). For each N , P (x|ξ N , X) denotes a posterior probability of a message x ∈ {0, 1} N when Alice used the basis X and Bob obtained outcome ξ N . Similarly, P (z|ξ N , Z) denotes a posterior probability of a message z ∈ {0, 1} N when Alice used the basis Z and Bob obtained ξ N .
Theorem 3 Let us consider a family of protocols indexed by the number of qubits N . Assume that for each N the size of Bob's quantum memory M , which may depend on N , is bounded as M ≤ qN for some q (0 ≤ q ≤ 1). For any p X and p Z satisfying q + p X + p Z < 1, there exists C 0 > 0 and ǫ > 0 such that for any ξ N , The above theorem shows that there is a non-trivial trade-off relation between P ({x|K(x|ρ X x,ξN , ξ N , X) ≤ p X N }|ξ N , X) and P ({z|K(z|ρ Z z,ξN , ξ N , Z) ≤ p Z N }|ξ N , Z) when q + p X + p Z < 1 holds. In particular, for sufficiently large N , if one of them is close to 1, the other becomes exponentially small. In other words, as there is a pair p X and p Z satisfying q + p X + p Z < 1 for any q < 1, there is a nontrivial effect of the bounded quantum memory for any q < 1.
The above theorem is derived from the following lemma.