82 citations · 191 across the 16 of their papers we have counts for
19 papers
One-shot quantum state redistribution and quantum Markov chains
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain +2
We revisit the task of quantum state redistribution in the one-shot setting, and design a protocol for this task with communication cost in terms of a measure of distance from quan…
Optical quantum communication complexity in the simultaneous message passing model
Ashutosh Marwah, Dave Touchette
The communication cost of a classical protocol is typically measured in terms of the number of bits communicated for this determines the time required for communication during the…
Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets
Debbie Leung, Ashwin Nayak, Ala Shayeghi +3
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for commun…
Incompressibility of classical distributions
Anurag Anshu, Debbie Leung, Dave Touchette
In blind compression of quantum states, a sender Alice is given a specimen of a quantum state drawn from a known ensemble (but without knowing what is), and she transmits s…
Erasable Bit Commitment from Temporary Quantum Trust
Norbert Lütkenhaus, Ashutosh S Marwah, Dave Touchette
We introduce a new setting for two-party cryptography with temporarily trusted third parties. In addition to Alice and Bob in this setting, there are additional third parties, whic…
Quantum Insertion-Deletion Channels
Janet Leahy, Dave Touchette, Penghui Yao
We introduce a model of quantum insertion-deletion (insdel) channels. Insdel channels are meant to represent, for example, synchronization errors arising in data transmission. In t…
Quantum Log-Approximate-Rank Conjecture is also False
Anurag Anshu, Naresh Goud Boddu, Dave Touchette
In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication compl…
Practical Quantum Appointment Scheduling
Dave Touchette, Benjamin Lovitz, Norbert Lütkenhaus
We propose a protocol based on coherent states and linear optics operations for solving the appointment-scheduling problem. Our main protocol leaks strictly less information about…
The Flow of Information in Interactive Quantum Protocols: the Cost of Forgetting
Mathieu Lauriere, Dave Touchette
In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important…
Exponential Separation of Quantum Communication and Classical Information
Anurag Anshu, Dave Touchette, Penghui Yao +1
We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the oth…
Augmented Index and Quantum Streaming Algorithms for DYCK(2)
Ashwin Nayak, Dave Touchette
We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with poten…
Quantum Advantage on Information Leakage for Equality
Juan Miguel Arrazola, Dave Touchette
We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in t…
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, Young Kun Ko +2
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with rounds, we prove a lower bound of $\…
Direct Sum Theorem for Bounded Round Quantum Communication Complexity
Dave Touchette
We prove a direct sum theorem for bounded round entanglement-assisted quantum communication complexity. To do so, we use the fully quantum definition for information cost and compl…
Smooth Entropy Bounds on One-Shot Quantum State Redistribution
Mario Berta, Matthias Christandl, Dave Touchette
In quantum state redistribution as introduced in [Luo and Devetak (2009)] and [Devetak and Yard (2008)], there are four systems of interest: the system held by Alice, the s…
Quantum Information Complexity and Amortized Communication
Dave Touchette
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum channels, and then investigate…
Noisy Interactive Quantum Communication
Gilles Brassard, Ashwin Nayak, Alain Tapp +2
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantu…
5-qubit quantum error correction in a charge qubit quantum computer
Dave Touchette, Haleemur Ali, Michael Hilke
We implement the DiVincenzo-Shor 5 qubit quantum error correcting code into a solid-state quantum register. The quantum register is a multi charge-qubit system in a semiconductor e…
Trade-off capacities of the quantum Hadamard channels
Kamil Bradler, Patrick Hayden, Dave Touchette +1
Coding theorems in quantum Shannon theory express the ultimate rates at which a sender can transmit information over a noisy quantum channel. More often than not, the known formula…