ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Mon, 09 Dec 2019 13:29:45 GMT2019-12-09T13:29:45Z50231- New bounds on classical and quantum one-way communication complexityhttps://scholarbank.nus.edu.sg/handle/10635/39441Title: New bounds on classical and quantum one-way communication complexity
Authors: Jain, R.; Zhang, S.
Abstract: In this paper we provide new bounds on classical and quantum distributional communication complexity in the two-party, one-way model of communication. In the classical one-way model, our bound extends the well known upper bound of Kremer, Nisan and Ron [I. Kremer, N. Nisan, D. Ron, On randomized one-round communication complexity, in: Proceedings of The 27th ACM Symposium on Theory of Computing, STOC, 1995, pp. 596-605] to include non-product distributions. Let ε{lunate} ∈ (0, 1 / 2) be a constant. We show that for a boolean function f : X × Y → {0, 1} and a non-product distribution μ on X × Y, D ε{lunate} 1, μ (f) = O ((I (X : Y) + 1) {dot operator} VC (f)), where D ε{lunate} 1, μ (f) represents the one-way distributional communication complexity of f with error at most ε{lunate} under μ; VC (f) represents the Vapnik-Chervonenkis dimension of f and I (X : Y) represents the mutual information, under μ, between the random inputs of the two parties. For a non-boolean function f : X × Y → {1, ..., k} (k ≥ 2 an integer), we show a similar upper bound on D ε{lunate} 1, μ (f) in terms of k, I (X : Y) and the pseudo-dimension of f ′ over(=, def) frac(f, k), a generalization of the VC-dimension for non-boolean functions. In the quantum one-way model we provide a lower bound on the distributional communication complexity, under product distributions, of a function f, in terms of the well studied complexity measure of f referred to as the rectangle bound or the corruption bound of f. We show for a non-boolean total function f : X × Y → Z and a product distribution μ on X × Y, Q ε{lunate}3 / 8 1, μ (f) = Ω (rec ε{lunate} 1, μ (f)), where Q ε{lunate}3 / 8 1, μ (f) represents the quantum one-way distributional communication complexity of f with error at most ε{lunate} 3 / 8 under μ and rec ε{lunate} 1, μ (f) represents the one-way rectangle bound of f with error at most ε{lunate} under μ. Similarly for a non-boolean partial function f : X × Y → Z ∪ {*} and a product distribution μ on X × Y, we show, Q ε{lunate}6 / (2 {dot operator} 1 54) 1, μ (f) = Ω (rec ε{lunate} 1, μ (f)) . © 2008 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394412009-01-01T00:00:00Z
- New results in the simultaneous message passing model via information theoretic techniqueshttps://scholarbank.nus.edu.sg/handle/10635/41155Title: New results in the simultaneous message passing model via information theoretic techniques
Authors: Jain, R.; Klauck, H.
Abstract: Consider the following Simultaneous Message Passing (SMP) model for computing a relation f ⊆ X × Y × ℤ. in this model Alice, on input x ∈ X and Bob, on input y ∈ Y, send one message each to a third party Referee who then outputs a z ∈ ℤ such that (x, y, z) ∈ f. We first show optimal Direct sum results for all relations f in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of f, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier Direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the Equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case. © 2009 IEEE.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411552009-01-01T00:00:00Z
- Efficient protocols for generating bipartite classical distributions and quantum stateshttps://scholarbank.nus.edu.sg/handle/10635/77850Title: Efficient protocols for generating bipartite classical distributions and quantum states
Authors: Jain, R.; Shi, Y.; Wei, Z.; Zhang, S.
Abstract: We investigate the fundamental problem of generating bipartite classical distributions or quantum states. By designing efficient communication protocols and proving their optimality, we establish a number of intriguing connections to fundamental measures in optimization, convex geometry, and information theory. 1) To generate a classical distribution P(x,y) , we tightly characterize the minimum amount of quantum communication needed by the psd-rank of P (as a matrix), a measure recently proposed by Fiorini et al. (Proc. 44th ACM Symp. Theory Comput., pp. 95-106, 2012) in studies of the minimum size of extended formulations of optimization problems such as TSP. This echos the previous characterization for the optimal classical communication cost by the nonnegative rank of P. The result is obtained via investigating the more general case of bipartite quantum state generation and designing an optimal protocol for it. 2) When an approximation of is allowed to generate a distribution (X,Y)∼ P, we present a classical protocol of the communication cost O((C(X,Y)+1)) , where C(X,Y) is common information, a well-studied measure in information theory introduced by Wyner (IEEE Trans. Inf. Theory, 21 (2):163-179, 1975). This also links nonnegative rank and common information, two seemingly unrelated quantities in different fields. 3) For approximately generating a quantum pure state , we completely characterize the minimum cost by a corresponding approximate rank, closing a possibly exponential gap left in Ambainis et al. (SIAM J. Comput., 32 (6):1570-1585, 2003). © 2013 IEEE.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/778502013-01-01T00:00:00Z
- A property of quantum relative entropy with an application to privacy in quantum communicationhttps://scholarbank.nus.edu.sg/handle/10635/39443Title: A property of quantum relative entropy with an application to privacy in quantum communication
Authors: Jain, R.; Radhakrishnan, J.; Sen, P.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394432009-01-01T00:00:00Z
- QIP = PSPACEhttps://scholarbank.nus.edu.sg/handle/10635/39317Title: QIP = PSPACE
Authors: Jain, R.; Ji, Z.; Upadhyay, S.; Watrous, J.
Abstract: The interactive proof system model of computation has been studied extensively in computational complexity theory and theoretical cryptography for more than 25 years, and has driven the development of interesting new techniques and insights in those fields. This work considers the quantum interactive proof system model, which is the classical model's natural quantum computational analog. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable with an ordinary classical computer using at most a polynomial amount of memory (or QIP = PSPACE in complexity-theoretic terminology). One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems. © 2010 ACM.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/393172010-01-01T00:00:00Z
- A direct product theorem for the two-party bounded-round public-coin communication complexityhttps://scholarbank.nus.edu.sg/handle/10635/40762Title: A direct product theorem for the two-party bounded-round public-coin communication complexity
Authors: Jain, R.; Pereszlenyi, A.; Yao, P.
Abstract: A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols [27], [18], [29], [20], [14]. Our result generalizes the result of Jain [11] which can be regarded as the special case when t = 1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain[11]. One key tool used in our work and also in Jain [11] is a message compression technique due to Braver man and Rao[5], who used it to show a direct sum theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein[9] for proving a parallel repetition theorem for two-prover games. © 2012 IEEE.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407622012-01-01T00:00:00Z
- A separation between divergence and Holevo information for ensembleshttps://scholarbank.nus.edu.sg/handle/10635/41153Title: A separation between divergence and Holevo information for ensembles
Authors: Jain, R.; Nayak, A.; Su, Y.
Abstract: The notion of divergence information of an ensemble of probability distributions was introduced by Jain, Radhakrishnan and Sen in Jain et al. (2002; 2009) in the context of the substate theorem. Since then, divergence has been recognised as a more natural measure of information in several situations in both quantum and classical communication. We construct ensembles of probability distributions for which divergence information may be significantly smaller than the more standard Holevo information. As a result, we establish that bounds previously shown for Holevo information are weaker than similar ones shown for divergence information. © 2010 Cambridge University Press.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411532010-01-01T00:00:00Z
- QIP = PSPACEhttps://scholarbank.nus.edu.sg/handle/10635/40740Title: QIP = PSPACE
Authors: Jain, R.; Ji, Z.; Upadhyay, S.; Watrous, J.
Abstract: This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model's natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations. © 2011.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/407402011-01-01T00:00:00Z
- Optimal direct sum results for deterministic and randomized decision tree complexityhttps://scholarbank.nus.edu.sg/handle/10635/43106Title: Optimal direct sum results for deterministic and randomized decision tree complexity
Authors: Jain, R.; Klauck, H.; Santha, M.
Abstract: A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions. © 2010 Elsevier B.V.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431062010-01-01T00:00:00Z
- Short proofs of the quantum substate theoremhttps://scholarbank.nus.edu.sg/handle/10635/39439Title: Short proofs of the quantum substate theorem
Authors: Jain, R.; Nayak, A.
Abstract: The Quantum Substate Theorem due to Jain (2002) gives us a powerful operational interpretation of relative entropy, in fact, of the observational divergence of two quantum states, a quantity that is related to their relative entropy. Informally, the theorem states that if the observational divergence between two quantum states ρ, σ is small, then there is a quantum state ρ′ close to ρ in trace distance, such that ρ′ when scaled down by a small factor becomes a substate of σ. We present new proofs of this theorem. The resulting statement is optimal up to a constant factor in its dependence on observational divergence. In addition, the proofs are both conceptually simpler and significantly shorter than the earlier proof. © 2012 IEEE.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394392012-01-01T00:00:00Z
- Parallel approximation of non-interactive zero-sum quantum gameshttps://scholarbank.nus.edu.sg/handle/10635/41154Title: Parallel approximation of non-interactive zero-sum quantum games
Authors: Jain, R.; Watrous, J.
Abstract: This paper studies a simple class of zero-sum games played by two competing quantum players: each player sends a mixed quantum state to a referee, who performs a joint measurement on the two states to determine the players' payoffs. We prove that an equilibrium point of any such game can be approximated by means of an efficient parallel algorithm, which implies that one-turn quantum refereed games, wherein the referee is specified by a quantum circuit, can be simulated in polynomial space. © 2009 IEEE.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411542009-01-01T00:00:00Z
- A parallel approximation algorithm for positive semidefinite programminghttps://scholarbank.nus.edu.sg/handle/10635/41152Title: A parallel approximation algorithm for positive semidefinite programming
Authors: Jain, R.; Yao, P.
Abstract: Positive semi definite programs are an important subclass of semi definite programs in which all matrices involved in the specification of the problem are positive semi definite and all scalars involved are non-negative. We present a parallel algorithm, which given an instance of a positive semi definite program of size N and an approximation factor ε > 0, runs in (parallel) time poly(1/ε)·polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1+ ε) to the optimal. Our result generalizes analogous result of Luby and Nisan (1993) for positive linear programs and our algorithm is inspired by their algorithm of [10]. © 2011 IEEE.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411522011-01-01T00:00:00Z
- Two-message quantum interactive proofs are in PSPACEhttps://scholarbank.nus.edu.sg/handle/10635/40123Title: Two-message quantum interactive proofs are in PSPACE
Authors: Jain, R.; Upadhyay, S.; Watrous, J.
Abstract: We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient parallel algorithm, based on the matrix multiplicative weights update method, for approximately solving a certain class of semidefinite programs. © 2009 IEEE.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/401232009-01-01T00:00:00Z
- The Communication complexity of correlationhttps://scholarbank.nus.edu.sg/handle/10635/39040Title: The Communication complexity of correlation
Authors: Harsha, P.; Jain, R.; McAllester, D.; Radhakrishnan, J.
Abstract: Let X and Y be finite nonempty sets and (X, Y) a pair of random variables taking values in X × Y. We consider communication protocols between two parties, ALICE and BOB, for generating X and Y. ALICE is provided an x ε X generated according to the distribution of X, and is required to send a message to BOB in order to enable him to generate y ε Y, whose distribution is the same as that of Y|X=x. Both parties have access to a shared random string generated in advance. Let T[X : Y] be the minimum (over all protocols) of the expected number of bits ALICE needs to transmit to achieve this. We show that I[X : Y] ≤ T[X : Y] ≤ I[X : Y] + 2 log2, (I[X : Y] + 1) + O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bits ALICE must transmit for the worst case x ε X. We show that the communication required in this case is related to the capacity C(E) of the channel E, derived from (X, Y ), that maps x ε X to the distribution of Y|X=x . We also show that the required communication T(E) satisfies C(E) ≤T(E) ≤ C(E) + 2log2(C(E) + 1) + O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719.2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other. © 2009 IEEE.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390402010-01-01T00:00:00Z
- Resource requirements of private quantum channels and consequences for oblivious remote state preparationhttps://scholarbank.nus.edu.sg/handle/10635/39438Title: Resource requirements of private quantum channels and consequences for oblivious remote state preparation
Authors: Jain, R.
Abstract: Shannon (Bell Syst. Tech. J. 27:623-656, 1948; Bell Syst. Tech. J. 28:656-715, 1949) in celebrated work had shown that n bits of shared key are necessary and sufficient to transmit n-bit classical information in an information-theoretically secure way, using one-way communication. Ambainis, Mosca, Tapp and de Wolf in (Proceedings of the 41st Annual IEEE Symposium on Foundation of Computer Science, pp. 547-553, 2000) considered a more general setting, referred to as private quantum channels, in which instead of classical information, quantum states are required to be transmitted and only one-way communication is allowed. They show that in this case 2n bits of shared key is necessary and sufficient to transmit an n-qubit state. We consider the most general setting in which we allow for all possible combinations, in one-way communication, i.e. we let the input to be transmitted, the message sent and the shared resources to be classical/quantum. We develop a general framework by which we are able to show simultaneously tight bounds on communication/shared resources in all of these cases and this includes the results of Shannon and Ambainis et al. As a consequence of our arguments we also show that in a one-way oblivious remote state preparation protocol for transferring an n-qubit pure state, the entropy of the communication must be 2n and the entanglement measure of the shared resource must be n. This generalizes the result of Leung and Shor (Phys. Rev. Lett. 90, 2003) which shows the same bound on the length of communication in the special case when the shared resource is maximally entangled, e.g. EPR pairs, and hence settles an open question asked in their paper regarding protocols without maximally entangled shared resource. © 2010 International Association for Cryptologic Research.
Sun, 01 Jan 2012 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394382012-01-01T00:00:00Z
- The partition bound for classical communication complexity and query complexityhttps://scholarbank.nus.edu.sg/handle/10635/40841Title: The partition bound for classical communication complexity and query complexity
Authors: Jain, R.; Klauck, H.
Abstract: We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the γ2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than the approximate polynomial degree and adversary bounds. © 2010 IEEE.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/408412010-01-01T00:00:00Z
- Efficient protocols for generating bipartite classical distributions and quantum stateshttps://scholarbank.nus.edu.sg/handle/10635/78120Title: Efficient protocols for generating bipartite classical distributions and quantum states
Authors: Jain, R.; Shi, Y.; Wei, Z.; Zhang, S.
Abstract: We investigate the fundamental problem of generating bipartite classical distributions or quantum states. By designing efficient communication protocols and proving their optimality, we establish a number of intriguing connections to fundamental measures in optimization, convex geometry, and information theory. 1. To generate a classical distribution P(x,y), we tightly characterize the minimum amount of quantum communication needed by the psd-rank of P (as a matrix), a measure recently proposed by Fiorini, Massar, Pokutta, Tiwary and de Wolf (Proceedings of the 44th ACM Symposium on Theory of Computing, pages 95-106, 2012) in studies of the minimum size of extended formulations of optimization problems such as TSP. This echos the previous characterization for the optimal classical communication cost by the nonnegative rank of P. The result is obtained via investigating the more general case of bipartite quantum state generation and designing an optimal protocol for it. 2. When an approximation of ε is allowed to generate a distribution (X, Y) ∼ P, we present a classical protocol of the communication cost O((C(X, Y) + 1)/ε), where C(X, Y) is common information, a well-studied measure in information theory introduced by Wyner (IEEE Transactions on Information Theory, 21(2):163-179, 1975). This also links nonnegative rank and common information, two seemingly unrelated quantities in different fields. 3. For approximately generating a quantum pure state |ψ〉, we completely characterize the minimum cost by a corresponding approximate rank, closing a possibly exponential gap left in Ambainis, Schulman, Ta-Shma, Vazirani and Wigderson. Copyright © SIAM.
Tue, 01 Jan 2013 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/781202013-01-01T00:00:00Z
- QIP = PSPACEhttps://scholarbank.nus.edu.sg/handle/10635/40807Title: QIP = PSPACE
Authors: Jain, R.; Ji, Z.; Upadhyay, S.; Watrous, J.
Abstract: We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows. © 2010 ACM.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/408072010-01-01T00:00:00Z
- Depth-independent lower bounds on the communication complexity of read-once Boolean formulashttps://scholarbank.nus.edu.sg/handle/10635/41159Title: Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
Authors: Jain, R.; Klauck, H.; Zhang, S.
Abstract: We show lower bounds of and Ω(n 1/4) on the randomized and quantum communication complexity, respectively, of all n-variable read-once Boolean formulas. Our results complement the recent lower bound of Ω(n/8 d ) by Leonardos and Saks [LS09] and Ω(n/2 O(dlogd)) by Jayram, Kopparty and Raghavendra [JKR09] for randomized communication complexity of read-once Boolean formulas with depth d. We obtain our result by "embedding" either the Disjointness problem or its complement in any given read-once Boolean formula. © 2010 Springer-Verlag Berlin Heidelberg.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/411592010-01-01T00:00:00Z
- Entanglement-resistant two-prover interactive proof systems and non-adaptive pir'shttps://scholarbank.nus.edu.sg/handle/10635/39440Title: Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's
Authors: Cleve, R.; Gavinsky, D.; Jain, R.
Abstract: We show that every language in NP is recognized by a two-prover interactive proof system with the following properties. The proof system is entanglement-resistant r;1-ε.1/2+ε[2], for any e such that 0 < ε < 1/4). Our result is based on the "oracularizing" property of a particular private information retrieval scheme (PIR), and it suggests that investigating related properties of other PIRs might bear further fruit.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/394402009-01-01T00:00:00Z
- Extension Complexity of Independent Set Polytopeshttps://scholarbank.nus.edu.sg/handle/10635/156683Title: Extension Complexity of Independent Set Polytopes
Authors: Goos, Mika; Jain, Rahul; Watson, Thomas
Abstract: We exhibit an $n$-node graph whose independent set polytope requires extended
formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit
examples of $n$-dimensional $0/1$-polytopes were known with extension
complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is
inspired by a relatively little-known connection between extended formulations
and (monotone) circuit depth.
Sat, 01 Oct 2016 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1566832016-10-01T00:00:00Z
- Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extractionhttps://scholarbank.nus.edu.sg/handle/10635/156684Title: Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction
Authors: Anshu, Anurag; Jain, Rahul; Warsi, Naqueeb Ahmad
Abstract: We consider the problem of quantum measurement compression with side
information in the one-shot setting with shared randomness. In this problem,
Alice shares a pure state with Reference and Bob and she performs a measurement
on her registers. She wishes to communicate the outcome of this measurement to
Bob using shared randomness and classical communication, in such a way that the
outcome that Bob receives is correctly correlated with Reference and Bob's own
registers. Our goal is to simultaneously minimize the classical communication
and randomness cost. We provide a protocol based on convex-split and position
based decoding with its communication upper bounded in terms of smooth max and
hypothesis testing relative entropies.
We also study the randomness cost of our protocol in both one-shot and
asymptotic and i.i.d. setting. By generalizing the convex-split technique to
incorporate pair-wise independent random variables, we show that our one shot
protocol requires small number of bits of shared randomness. This allows us to
construct a new protocol in the asymptotic and i.i.d. setting, which is optimal
in both the number of bits of communication and the number of bits of shared
randomness required.
We construct a new protocol for the task of strong randomness extraction in
the presence of quantum side information. Our protocol achieves error guarantee
in terms of relative entropy (as opposed to trace distance) and extracts close
to optimal number of uniform bits. As an application, we provide new
achievability result for the task of quantum measurement compression without
feedback, in which Alice does not need to know the outcome of the measurement.
This leads to the optimal number of bits communicated and number of bits of
shared randomness required, for this task in the asymptotic and i.i.d. setting.
Tue, 01 Jan 2019 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1566842019-01-01T00:00:00Z
- On the near-optimality of one-shot classical communication over quantum channelshttps://scholarbank.nus.edu.sg/handle/10635/159545Title: On the near-optimality of one-shot classical communication over quantum channels
Authors: Anshu, Anurag; RAHUL JAIN; NAQUEEB AHMAD WARSI
Abstract: © 2019 Author(s). We study the problem of transmission of classical messages through a quantum channel in several network scenarios in the one-shot setting. We consider both the entanglement assisted and unassisted cases for the point to point quantum channel, the quantum multiple-access channel, the quantum channel with a state, and the quantum broadcast channel. We show that it is possible to near-optimally characterize the amount of communication that can be transmitted in these scenarios, using the position-based decoding strategy introduced in a prior study (A. Anshu, R. Jain, and N. Warsi, https://ieee.org/document/8399830). In the process, we provide a short and elementary proof of the converse for entanglement-assisted quantum channel coding in terms of the quantum hypothesis testing divergence [obtained earlier in the work of W. Matthews and S. Wehner, IEEE Trans. Inf. Theory 60, 7317-7329 (2014)]. Our proof has the additional utility that it naturally extends to various network scenarios mentioned above. Furthermore, none of our achievability results require a simultaneous decoding strategy, existence of which is an important open question in quantum Shannon theory.
Tue, 01 Jan 2019 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1595452019-01-01T00:00:00Z