Rahul Jain
Email Address
dcsrahul@nus.edu.sg
26 results
Publication Search Results
Now showing 1 - 10 of 26
Publication QIP = PSPACE(2010) Jain, R.; Ji, Z.; Upadhyay, S.; Watrous, J.; COMPUTER SCIENCEThe 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.Publication New results in the simultaneous message passing model via information theoretic techniques(2009) Jain, R.; Klauck, H.; COMPUTER SCIENCEConsider 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.Publication Two-message quantum interactive proofs are in PSPACE(2009) Jain, R.; Upadhyay, S.; Watrous, J.; COMPUTER SCIENCEWe 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.Publication New bounds on classical and quantum one-way communication complexity(2009) Jain, R.; Zhang, S.; COMPUTER SCIENCEIn 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.Publication A parallel approximation algorithm for positive semidefinite programming(2011) Jain, R.; Yao, P.; COMPUTER SCIENCEPositive 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.Publication Resource requirements of private quantum channels and consequences for oblivious remote state preparation(2012) Jain, R.; COMPUTER SCIENCEShannon (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.Publication Efficient protocols for generating bipartite classical distributions and quantum states(2013) Jain, R.; Shi, Y.; Wei, Z.; Zhang, S.; CENTRE FOR QUANTUM TECHNOLOGIES; COMPUTER SCIENCEWe 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.Publication Depth-independent lower bounds on the communication complexity of read-once Boolean formulas(2010) Jain, R.; Klauck, H.; Zhang, S.; COMPUTER SCIENCEWe 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.Publication A property of quantum relative entropy with an application to privacy in quantum communication(2009) Jain, R.; Radhakrishnan, J.; Sen, P.; COMPUTER SCIENCEPublication Short proofs of the quantum substate theorem(2012) Jain, R.; Nayak, A.; COMPUTER SCIENCEThe 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.
- «
- 1 (current)
- 2
- 3
- »