Guessing and Certifying Information
in Quantum Systems
DEPARTMENT OF APPLIED MATHEMATICS, HANYANG UNIVERSITY (ERICA), ANSAN, KOREAY
When quantum systems are applied to information processing such as computational or communication tasks, it is essential to find feasible methods of manipulating quantum systems for such purposes. These include extracting maximal information from given quantum systems, describing how information between system and environment is processed during dynamics, and certifying the existence of useful resources such as entanglement. We here provide an overview on the on-going efforts in these areas, namely, the optimal guessing with quantum side information, the operational characterisation of the dynamics of open quantum systems, and feasible and efficient methods for detecting entangled states.
Quantum theory is so fundamental that it is behind of all classical systems as well as their information processing. In quantum information theory, the postulates of quantum theory are directly applied to information processing and lead to advantages over their classical counterparts. For instance, exponential speedup has been shown in the prime factorisation problem  and general security can be obtained in cryptographic systems [2,3].
One of the distinguished properties of quantum systems, and also interesting compared to their classical counterparts, is the dynamical aspect, namely, that quantum dynamics should correspond to a linear, positive, and completely positive transformation over quantum states. For classical systems, dynamics can be often non-linear, and there is no reason to ask the condition of complete positivity since positive transformation is immediately completely positive. This shares some similarity to what appears in the static aspect of multipartite quantum systems, that is, entanglement, which describes essentially quantum correlations having no classical counterpart. In classical systems, bipartite correlations are the joint probability distribution of local systems. Entanglement of bipartite quantum systems is even stronger, beyond joint probability distributions. Thus, classical correlations remain valid under positive transformations, whereas quantum correlations do so under completely positive transformations.
In fact, the characterisation of quantum dynamics can be seen as a dual to entangled states . The condition of being completely positive for quantum dynamical maps takes into account entanglement between system of interest and the surrounding environment: if a map is only positive but not completely positive, it would lead to a non-positive operator describing the system and environment, which has no way of being interpreted as a quantum state. This also implies that quantum dynamics cannot generate arbitrary entangled states under quantum principles. This is closely connected to the information task of quantum systems, secure quantum communication, where entanglement among three parties, two honest parties and an eavesdropper, cannot be arbitrarily formed but restricted to those satisfying the constraints from quantum postulates, such as monogamous relations. That is, once quantum systems are applied to distributing information to legitimate parties, the maximal information that can be delivered is constrained by the principles of quantum theory.
Here I describe recent and on-going research along the lines of, i) characterisation of maximal information that can be obtained from quantum systems, ii) the description of information processing between system and environment, and iii) detecting the presence of entanglement in given quantum systems. The maximal information is characterised by the min-entropy, for which the operational task corresponds to optimal quantum state discrimination and the figure of merit is the guessing probability about an ensemble of quantum states, i.e. the highest success probability of making correct guesses on average. Recently, a new theoretical tool, the so-called information flow that applies quantum state discrimination, has been developed to describe quantum Markovian systems. This is closely related to entanglement between system and environment. Finally, we present the recent efforts in efficient and feasible methods of detecting entangled states.
OPTIMAL GUESSING WITH QUANTUM SIDE INFORMATION
Suppose that quantum states are given with a priori probabilities, respectively, as an ensemble. Among possible scenarios of extracting information from the ensemble, the well-known and celebrated Holevo quantity serves as the upper bound to the so-called accessible information that quantifies the number of distinguishable states on average . It therefore provides the maximal information that can be extracted on average from the ensemble.
The so-called min-entropy has been introduced as the information-theoretic measure that quantifies the maximal information that can be extracted in a one-shot scenario . It is defined as the logarithm of the inverse of the most probable probability, and quantifies the randomness of a given random variable . The conditional min-entropy, given quantum side information, characterises the maximal information that can be extracted from quantum systems in a one-shot scenario, also giving the upper bound to the Holevo quantity. It turns out that the operational task corresponding to conditional min-entropy is optimal quantum state discrimination that aims to, among the ensemble, maximise the probability of making correct guesses on average . The scenario is also referred to as minimum-error quantum state discrimination.
In the problem of minimum-error quantum state discrimination, Helstrom has shown the general solution for cases of two quantum states given arbitrary a priori probabilities . The maximal probability of making a correct guess is called the guessing probability. It is shown that the guessing probability is proportional to the trace distance of the two given quantum states. However, for more than two-state discrimination, the guessing probability is in general not known unless specific symmetries are assumed for the given quantum states, for instance, geometrically uniform structure.
Fig. 1: Qubit state discrimination with equal a priori probabilities is completely solved .
In Ref. , optimal quantum state discrimination is analysed and its general structure is presented. Thus, optimal quantum state discrimination is no longer an optimisation problem but introduced as a problem of finding parameters that satisfy a list of equality conditions. This is called the complementarity problem. The approach is generally considered harder than primal and dual optimisation problems since it contains more parameters. The usefulness lies in the fact that it provides a general structure for the problem. It is also found that the guessing probability for N states is in general given by a random guess, denoted by 1/N, plus the averaged trace distance of complementary parameters.
With the complementarity problem, optimal discrimination of qubit states is completely solved when the a priori probabilities are equal . In Fig. 1, an arbitrary set of qubit states is shown and the guessing probability can be obtained by the geometric method in Ref. . Then, the guessing probability for the qubit states is immediately found. This in fact solves a long-standing open question in quantum information theory.
Quantum state discrimination is a fundamental problem connected to a number of practical quantum information applications. The results obtained in Ref.  found the general structure of optimal quantum state discrimination and show general solutions to a set of quantum states containing no symmetry.
OPERATIONAL CHARACTERISATION OF DY-NAMICS OF OPEN QUANTUM SYSTEMS
One of the important properties of dynamics is to understand the so-called memory effects of dynamics, dubbed Markovianity when no memory effect is assigned . This property is also closely related to cryptographic scenarios: a Markov process guarantees no security at all and serves as an insecurity condition .
In the traditional approach of characterising Markovian dynamics, Markovianity assumptions such as weak-coupling assumptions and the Born-Markov approximation have been applied, and then quantum Markovian dynamics could be found in the form of the master equation . Then, the decay rate determines if a given system is under Markovian or non-Markovian evolution: negative values in decay rates indicate non-Markovianity of dynamics. This description also contains a couple of open questions, such as the relation between generator and master equations .
Operational characterisation of Markovianity
Optimal quantum state discrimination has been recently applied to characterisation of the quantum Markov process . This is remarkable in that this approach has obtained an operational characterisation of Markovianity of quantum dynamics, that is defined in an axiomatic way as a linear, positive, and completely positive map. Since it is an operational characterisation, one can also devise a method for detecting non-Markovianity of quantum dynamics without identification of the given dynamics via process tomography.
To be precise, the characterisation is given with the so-called information flow that is defined as the time-rate of the trace distance of a pair of quantum states under a given evolution. Then, the evolution is Markovian if the time-rate of the trace distance does not decrease for any pair of quantum states .
It is also found that the operational definition of Marko-vianity based on the notion of information flow does not fit into the traditional one, i.e., in terms of decay rates. In an axiomatic way, also following a classical analogy of Markov chains for probabilistic systems, the so-called CP divisibility that respects the semigroup structure has also been suggested for the characterisation of quantum Markovian dynamics, where a dynamical map is called CP divisible if it can be concatenated by a dynamical map and completely positive (CP) propagator.
Operational characterisation to divisible maps
Then, generalising the notion of divisibility, a finer structure has been found with so-called k-divisible maps, where k-divisible maps contain k-positive propagators when a dynamical map is decomposed into the concatenation . When k is equal to 1 it is called P divisible, and when k is infinite, it is called CP divisible. Note that we have assumed that there exists a propagator in the description of a dynamical map. In terms of k-divisible maps, when divisibility is possible, the operational definition with information flow corresponds to P divisibility, and the other to CP divisibility. In this way, one can identify information flow as the operational quantity that signifies P divisibility of dynamical maps.
In Ref. , the operational quantity that signifies k-divisibility has been characterised in terms of quantum channel discrimination. Namely, it is shown that a map is k-divisible if and only if for any pair of quantum channels, the distinguishability of the channels under a given evolution with quantum states having Schmidt rank not larger than k does not increase. The radical difference is that, instead of quantum state discrimination, quantum channel discrimination is exploited. In this way, entanglement is naturally embedded into the problem.
Fig. 2: Channel distinguishability can be improved by applying entangled states, while state distinguishability is not.
It is worth noting that quantum channel discrimination enjoys the advantage of applying entanglement to improve channel distinguishability, whereas quantum state discrimination cannot be improved by an entangled input [16,17,18]. Then, distinguishability of quantum channels can be improved by applying entangled states, in contrast to the case of quantum state discrimination. Depending on entanglement of input states, distinguishability of channels can be structured, see Fig. 3. Here, we apply as an entanglement measure the Schmidt number, which runs from 1 to d where Schmidt number 1 means separable states and Schmidt number d means maximally entangled. It is an entanglement measure in that it does not increase under local operations and classical communication. In Fig. 3, it is shown that the more entangled an input state is, the more it has higher distinguishability.
Fig. 3: Q with subscript k denotes a set of quantum states having Schmidt number less than or equal to k. According to entanglement of input states, distinguishability is structured. The more entangled an input state is, the more useful it is for channel discrimination.
It is shown that k-divisible dynamical maps are characterised by channel distinguishability. For k-divisible maps, channel distinguishability with Schmidt number not larger than k does not increase in time for any pair of quantum channels . All these can be equivalently described in terms of conditional min-entropy with quantum side information from the relation between conditional min-entropy and the distinguishability of quantum states .
EFFICIENT METHODS OF DETECTING ENTAN-GLED STATES
Properties of quantum systems can be found by detecting specific observable quantities experimentally. In the case of Markovianity shown in the above, from the operational characterisation, measurement that distinguishes quantum states or quantum channels should be performed. The full characterisation via tomography is not necessary. We recall that for channel distinguishability, one has to apply entangled input states to achieve optimal discrimination. This naturally introduces the problem of entanglement detection, which is, in fact, of general importance as well.
As is mentioned above, entangled states are characterised by positive but not completely positive maps. It is clear that these maps cannot be realised experimentally since physical processes corresponds only to positive and completely positive maps. For this reason, an alternative approach has been devised using entanglement witnesses (EWs) which can be factorised into local observables [19,20]. That is, EWs are local observables such that the expectation is negative for some entangled states and non-negative for all separable states. Thus, negative expectation values obtained in experiment certify unambiguously that a given state is entangled. Note also that EWs can directly detect entangled states even before the identification of quantum states via state tomography.
The disadvantage of EWs lies in the efficiency of detecting entangled states. Simply said, there is not a single EW that detects all entangled states, whereas a single map, the partial transposition, can detect all two-qubit entangled states.
Fig. 4: The approximate partial transposition is implemented for two-photon polarisation qubit states with local operations and classical communication. Quantum operations in (b) and (c) can be performed locally, and are admixed with some probability such that they compose the map in (a) .
Physical approximations to partial transpose
In Ref. , a physical approximation to partial transposition has been proposed for efficient and direct detection of entangled states. This applies a so-called structural physical approximation (SPA), that admixes the depolarisation channel to a positive map such that the resulting one is completely positive, corresponding to a physical process that can be realised experimentally. The method of entanglement detection involves collective measurement that requires the ability to store quantum states for a while, that is quantum memory, which however remains experimentally challenging. Thus, the original proposed scheme is not feasible experimentally.
Fig. 5: The SPAed partial transposistion has been applied to four Bell states. The first column shows four Bell states, the second the resulting states after partial transposition, and the third one experiment results with SPAed partial transposition .
Thus, it is shown that SPA to partial transposition is entanglement-breaking for qubit systems  and in fact high-dimensional systems in general . This implies SPA to partial transposistion is an immediately measure-and-prepare scheme and, thus, once the SPAed map is realised experimentally, it may be applied to detecting entangled states without quantum memory.
Based on theory , it is possible to devise a method of realising approximate positive maps experimentally. The proof-of-principle demonstration for the SPAed partial transposition for two-qubit states has been performed for photonic devices . The implementation is performed with local operations and classical communication, see Fig. 4. The operation is applied to four Bell states, maximally entangled ones, and the experimental result is shown in Fig. 5.
Note that the results in Ref.  cannot be applied to entanglement detection yet but only show a proof-of-principle demonstration to realise the SPAed partial transposition. For detecting entangled states, the scheme needs to be combined with the spectrum estimation technique, that now corresponds to a post-processing of measurement outcomes.
Minimal scheme for entanglement detection
So far it has been discussed how SPA leads to the implementation of a physical process that optimally approximates positive but not completely positive maps. SPA is also useful to devise a minimal scheme of detecting entangled states. In practical applications of EWs, the long-standing question has been the comparison of resources required for EWs and quantum state tomography. This is also due to the inefficiency of detecting entangled states by EWs.
The comparison can be put as follows. Suppose that there are copies of unknown quantum states, and a number of detectors can be applied to measurement. The goal is to find if the state is entangled. Experimentalists have two options, one applying EWs and the other state tomography. Once tomography is performed and the state is completely identified, a number of theoretical methods of detecting entangled states can be applied , such as a numerical method involving a semidefinite program. This, in fact, completely determines if a given state is entangled, or separable.
Or, the detectors may be exploited to construct EWs which, without tomography, can directly detect entangled states. However, when EWs do not show negative expectation, it is not clear whether the given states are separable, or not. Moreover, EWs are not generally efficient for detecting entangled states. Thus, from a practical point of view, it may happen that repeating applications of EWs would cost more experimental resources than quantum state tomography, given that, after state verification via tomography, theoretical tools to detect entangled states are much more accessible than repetitions of experiment.
In this sense, one may consider EWs as partial tomography. That is, repeating experiment with EWs a couple of times would achieve reconstruction of the quantum states. Then, a crucial question is to compare minimal resources for realising EWs and tomography: namely, what are the minimal experimental resources needed in order to construct a single EW such that they do not reach quantum state tomography yet? Recently, it has been shown in Ref.  that the answer is that they are simply two detectors. More precisely, they are two detectors of a Hong-Ou-Mandel interferometer.
Fig. 6: Minimal scheme for detecting entangled states is shown using two detectors in a Hong-Ou-Mandel interferometer . Entanglement detection works by quantum joining, that maps two-photon states into a single photon's degrees of freedom including the orbital-angular-momentum states.
In Fig. 6, the scheme is presented , together with a novel technique called quantum joining . The key concept of entanglement detection with SPA to EWs is that SPA introduces a way of transforming a non-positive operator into a positive operator that can be interpreted as a quantum state. Then, to estimate the expectation of EWs, one does not have to find a decomposition of EWs with detectors any more but, by SPA to EWs, can connect EWs to preparation of a quantum state. Thus, after all, what is measured experimentally is the expectation of the positive operator, SPAed EWs, which can be done with interferometry. Thus, the scheme in Fig. 6 uses a Hong-Ou-Mandel interferometer that contains only two detectors.
We have considered fundamental operations in quantum information applications. Firstly, we have considered the extraction of maximal information from quantum systems in a one-shot scenario. Its operational task corresponds to minimum-error quantum state discrimination, where the maximal success probability of making a correct guess is denoted by the guessing probability. Then, we discussed the general properties of the guessing probability for an arbitrary set of quantum states.
It has been found recently that optimal quantum state discrimination achieves the operational characterisation of Markovian dynamics. When a dynamical map has a propagator, one can introduce k-divisible maps. Then, it has been found that the operational characterisation of k-divisible maps can be obtained by quantum channel discrimination with entangled states having Schmidt number not larger than k. Since all these characterisations have operational meaning, they can be applied to the experimental detection of non-Markovian or indivisible dynamics.
Finally, we have reviewed the recent progress of applying the SPA to maps and EWs, and their related applications in entanglement detection. On the one hand, a useful map for entanglement detection such as the SPAed partial transposition can now be realised experimentally. For instance, the SPAed partial transposition has been realised with two-photon states . On the other hand, when SPA is applied to EWs it is shown that minimal resources for realising EWs for entanglement detection requires only two detectors. This contrasts with quantum state tomography, where, as dimensions and the number of parties increase, the number of detectors increases exponentially, whereas when applying SPA to EWs the number of detectors for detecting entangled states is fixed to two detectors, which are actually from Hong-Ou-Mandel interferometry.
We envisage the results presented would be applied to practical quantum information tasks. The general properties of optimal quantum state discrimination is connected to a number of protocols. The operational characterisation of k-divisibility may open a new avenue to investigating correlation between system and environment under quantum evolution. It would also be interesting to realise two-detector entanglement detection experimentally.
Acknowledgement: This work is supported by an Institute for Information & Communications Technology Promotion(IITP) grant funded by the Korean government(MSIP) (No.R 0190-15-2028, PSQKD) and the KIST Institutional Program (Project No. 2E26680-16-P025).
 P. W. Shor, SIAM J. Comput., 26 (5): 1484-1509 (1997).
 C. H. Bennett and G. Brassard. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 175, 8.
New York, 1984.
 A. Ekert, Phys. Rev. Letts., 67, 661, (1991).
 M., P., and R., Horodecki, Phys. Letts. A 223, 1 (1996).
 A. S. Holevo, Problems of Information Transmission 9 177 (1973).
 R. Renner, PhD thesis, ETH (2005).
 R. Koenig, R. Renner, and C. Schaffner, IEEE Trans. Inf. Th., vol. 55, no. 9 (2009).
 C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976), Vol. 123.
 J. Bae, New J. Phys. 15 073037 (2013).
 J. Bae and W.-Y, Hwang, Phys. Rev. A 87, 012334 (2013).
 H. P. Breuer and F. Petruccione, The Theory of Open Quantum Systems, Oxford University Press (2002).
 U.Maurer, IEEE Trans. Inf. Theory, 39 733, (1993).
 H. P. Breuer, E. M. Laine and J. Piilo, Phys. Rev. Letts. 103, 210401 (2009).
 D. Chruscinski and S. Maniscalco, Phys. Rev. Lett. 112, 120404 (2014).
 J. Bae and D. Chruscinski, Phys. Rev. Lett. 117, 050403 (2016).
 A. Acin, Phys. Rev. Lett. 87, 177901 (2001).
 G. M. D'Ariano, P. LoPresti, and M. G. A. Paris, Phys. Rev. Lett. 87, 270404 (2001).
 M. Piani and J. Watrous, Phys. Rev. Lett. 102, 250501 (2009).
 O. Guhne and G. Toth, Physics Reports 474, 1 (2009).
 D. Chruscinski and G. Sarbicki, J. Phys. A: Math. Theor. 47, 483001 (2014).
 P. Horodecki and A. Ekert, Phys. Rev. Lett. 89, 127902 (2002).
 J. Fiurasek, Phys. Rev. A 66 052315 (2002).
 J. K. Korbicz, M. L. Almeida, J. Bae, M. Lewenstein, and A. Acin, Phys. Rev. A 78, 062105 (2008).
 H.-T. Lim, Y.-S. Kim, Y.-S. Ra, J. Bae, and Y.-H. Kim, Phys. Rev. Lett. 107, 160401 (2011).
 R., P., M., and K. Horodecki, Rev. Mod. Phys.81 865 (2009).
 C. J. Kwong, S. Felicetti, and L.-C. Kwek, and J. Bae, arXiv:1606.00427.
 C. Vitelli et. al., Nature Photonics, 1, 521, (2013).
Joonwoo Bae obtained a PhD from the Departament d`Estructura i Constituents de la Materia (ECM) at Universitat de Barcelona in 2007 while preparing the thesis work entitled Entanglement and Quantum Crypotography at the Institute of Photonic Sciences (ICFO). He worked at the Korea Institute for Advanced Study (KIAS) from 2007 to 2011 as a research fellow while also at the same time undertaking national service. From 2011 to 2014 he worked at the Centre for Quantum Technologies (CQT) at the National Univ. of Singapore and was a visiting researcher at ICFO. In 2014. he joined Freiburg Institute for Advanced Studies (FRIAS) at Albert-Ludwig University of Freiburg in Germany as a Junior Fellow, co-funded Marie Curie Fellow. Since 2015, he has been with Dept. of Applied Mathematics at Hanyang University (ERICA), Ansan, Korea, working in the field of quantum information theory.