Pranab Sen

STOC Conference 2011 Conference Paper

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

• Omar Fawzi
• Patrick M. Hayden
• Pranab Sen

STOC Conference 2006 Conference Paper

Limitations of quantum coset states for graph isomorphism

• Sean Hallgren
• Cristopher Moore
• Martin Rötteler
• Alexander Russell
• Pranab Sen

FOCS Conference 2003 Conference Paper

A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness

• Rahul Jain 0001
• Jaikumar Radhakrishnan
• Pranab Sen

We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/, .. ., X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/. .. /spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/: 2/sup [n]/ /spl rarr/ {0, 1}, such that F(X/sub 1/, .. ., X/sub t/) = f/sub F/(X/sub 1/ /spl cap/. .. /spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i: f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).

STOC Conference 2003 Conference Paper

Hidden translation and orbit coset in quantum computing

• Katalin Friedl
• Gábor Ivanyos
• Frédéric Magniez
• Miklos Santha
• Pranab Sen

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z p n , whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup , and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N , for any solvable normal subgroup N of G .

MFCS Conference 2003 Conference Paper

Quantum Testers for Hidden Group Properties

• Katalin Friedl
• Frédéric Magniez
• Miklos Santha
• Pranab Sen

Abstract We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup.

FOCS Conference 2002 Conference Paper

Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States

• Rahul Jain 0001
• Jaikumar Radhakrishnan
• Pranab Sen

We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(/spl rho//spl par//spl sigma/)/spl Delta/=Tr /spl rho/(log /spl rho/-log /spl sigma/), of two quantum states /spl rho/ and /spl sigma/ is at most c, then /spl rho//2/sup O(c)/ 'sits inside' /spl sigma/. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.

FOCS Conference 2000 Conference Paper

The Quantum Complexity of Set Membership

• Jaikumar Radhakrishnan
• Pranab Sen
• Srinivasan Venkatesh 0001

Studies the quantum complexity of the static set membership problem: given a subset S (|S|/spl les/n) of a universe of size m(/spl Gt/n), store it as a table, T: (0, 1)/sup r//spl rarr/(0, 1), of bits so that queries of the form 'is x in S? ' can be answered. The goal is to use a small table and yet answer queries using a few bit probes. This problem was considered by H. Buhrman et al. (2000), who showed lower and upper bounds for this problem in the classical deterministic and randomised models. In this paper, we formulate this problem in the "quantum bit-probe model". We assume that access to the table T is provided by means of a black-box (oracle) unitary transform O/sub T/ that takes the basis state (y, b) to the basis state |y, b/spl oplus/T(y)>. The query algorithm is allowed to apply O/sub T/ on any superposition of basis states. We show tradeoff results between the space (defined as 2/sup r/) and the number of probes (oracle calls) in this model. Our results show that the lower bounds shown by Buhrman et al. for the classical model also hold (with minor differences) in the quantum bit-probe model. These bounds almost match the classical upper bounds. Our lower bounds are proved using linear algebraic arguments.