Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Efficient methods for one-shot quantum communication

Anurag Anshu

Published Jan 1, 2020• 4 citations
Publisher

Abstract

We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two new methods to achieve this, the first method involving two new versions of the convex-split lemma that use much smaller amount of additional resource (in comparison to previous version) and the second method being inspired by the technique of classical correlated sampling in computer science literature. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(nlog n) and depth poly(log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. Furthermore, the number of qubits of pre-shared entanglement is exponentially smaller than that used in the previous protocol that was near-optimal in communication. We also achieve similar results for the one-shot quantum state redistribution. Joint work with Rahul Jain. https://arxiv.org/abs/1809.07056

DOI
10.14288/1.0388334

Related papers

Efficient methods for one-shot quantum communication

Anurag Anshu, Rahul Jain

Abstract We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two methods for this; the first constructs a resource-efficient convex-split lemma and the second adapts the technique of classical correlated sampling in computer science literature. These lead to the following consequences in one-shot quantum information theory. First concerns the task of quantum decoupling, achieved in many previous works with the aid of a random or pseudo-random unitary. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner; furthermore our unitary performs addition and multiplication modulo a prime. As the second consequence, we construct near-optimal communication protocol for quantum channel coding that uses exponentially smaller entanglement than the previous near-optimal protocol.

arXiv:1809.07056•npj Quantum Information•Aug 20, 2022•12 citations

Near optimal bounds on quantum communication complexity of single-shot quantum state redistribution

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain

We show near optimal bounds on the worst case quantum communication of single-shot entanglement-assisted one-way quantum communication protocols for the {\em quantum state redistribution} task and for the sub-tasks {\em quantum state splitting} and {\em quantum state merging}. Our bounds are tighter than previously known best bounds for the latter two sub-tasks. A key technical tool that we use is a {\em convex-split} lemma which may be of independent interest.

•Oct 11, 2014•10 citations

New methods for Quantum Compiling

Vadym Kliuchnikov

The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.

•Apr 30, 2014•3 citations

On the near-optimality of one-shot classical communication over quantum channels

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

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.

arXiv:1804.09644•Journal of Mathematical Physics•Jan 1, 2019•27 citations

The Power of One Clean Qubit in Communication Complexity

Hartmut Klauck, Debbie Lim

We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.

arXiv:1807.07762•Leibniz international proceedings in informatics•Jul 20, 2018•2 citations

One-Shot Quantum State Redistribution and Quantum Markov Chains

Anurag Anshu, Shima Bab Hadiashar, Rahul Jain +2 more

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 quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to operationally connect one-shot quantum state redistribution and quantum Markov chains, and can be interpreted as an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. Thus, our work takes a step towards the important open question of near-optimal characterization of the one-shot quantum state redistribution. A full version of this paper is accessible at: https://arxiv.org/pdf/2104.08753.pdf

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•2 citations
We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two new methods to achieve this, the first method involving two new versions of the convex-split lemma that use much smaller amount of additional resource (in comparison to previous version) and the second method being inspired by the technique of classical correlated sampling in computer science literature. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(nlog n) and depth poly(log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. Furthermore, the number of qubits of pre-shared entanglement is exponentially smaller than that used in the previous protocol that was near-optimal in communication. We also achieve similar results for the one-shot quantum state redistribution. Joint work with Rahul Jain. https://arxiv.org/abs/1809.07056
Abstract We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two methods for this; the first constructs a resource-efficient convex-split lemma and the second adapts the technique of classical correlated sampling in computer science literature. These lead to the following consequences in one-shot quantum information theory. First concerns the task of quantum decoupling, achieved in many previous works with the aid of a random or pseudo-random unitary. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a ‘classical’ manner; furthermore our unitary performs addition and multiplication modulo a prime. As the second consequence, we construct near-optimal communication protocol for quantum channel coding that uses exponentially smaller entanglement than the previous near-optimal protocol.
The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.
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.
We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.
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 quantum Markov chains. More precisely, the distance is defined in terms of quantum max-relative entropy and quantum hypothesis testing entropy. Our result is the first to operationally connect one-shot quantum state redistribution and quantum Markov chains, and can be interpreted as an operational interpretation for a possible one-shot analogue of quantum conditional mutual information. The communication cost of our protocol is lower than all previously known ones and asymptotically achieves the well-known rate of quantum conditional mutual information. Thus, our work takes a step towards the important open question of near-optimal characterization of the one-shot quantum state redistribution. A full version of this paper is accessible at: https://arxiv.org/pdf/2104.08753.pdf