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

arXiv:2506.19369 · Physical Review A

Gottesman-Knill limit on one-way communication complexity: Tracing the quantum advantage down to magic resources

Snehasish Roy Chowdhury, Sahil Gopalkrishna Naik, Ananya Chakraborty, Ram Krishna Patra, Subhendu B. Ghosh, Pratik Ghosal, Manik Banik, Ananda G. Maity

Published Mar 20, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.

DOI
10.1103/x741-4kd1

Related papers

No-broadcasting of magic states

Zijian Zhang, Lingxuan Feng, Shunlong Luo

From both intuitive and physical perspectives, it is generally recognized that within a resource theory framework, free operations cannot broadcast a resource state due to their inability to generate resource from free states. In the stabilizer formalism of fault-tolerant quantum computation, the basic ingredients of the corresponding resource theory consist of stabilizer states as free states and stabilizer operations as free operations. The celebrated Gottesman-Knill theorem shows that quantum advantages over classical computation come from the magic (nonstabilizer) resource, such as magic states or non-Clifford gates. In this work, we prove that broadcasting of any magic state via stabilizer operations is impossible, which is reminiscent of the no-broadcasting theorems for noncommuting states or quantum correlations. We further derive a trade-off relation between the magic resource consumed in the initial system and that gained in the target system. These results characterize magic states in the stabilizer formalism from the broadcasting angle, and may have implications for distributed quantum computation and quantum secret sharing.

Physical Review A•Jul 25, 2024•9 citations

Unbounded quantum advantage in communication complexity measured by distinguishability

Satyaki Manna, Anubhav Chaturvedi, Debashis Saha

Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values. Published by the American Physical Society 2024

arXiv:2401.12903•Physical Review Research•Dec 12, 2024•9 citations

Entanglement assisted communication complexity measured by distinguishability

Satyaki Manna, Ankush Pandit, Anubhav Chaturvedi +1 more

We investigate the quantum advantage that can arise in typical two-party communication scenarios, where the sender and the receiver are allowed to share prior correlations. Focusing on communication tasks constrained by the distinguishability of the sender's inputs, we demonstrate that entanglement-assisted communication with both classical and quantum message can outperform classical communication supplemented with shared randomness. We begin by developing a general framework for communication tasks with pre-shared correlations. Within this framework, we establish an equivalence among entanglement-assisted classical communication, entanglement-assisted quantum communication, and quantum communication, showing that no hierarchy exists between these three paradigms. We then investigate the scenario where the receiver has no input and prove that no advantage can arise in this case. However, an advantage in the entanglement-assisted setting emerges once additional constraints are imposed on the dimension of the communicated message. This further highlights the superiority of entanglement-assisted classical communication over standard quantum communication. Then we demonstrate several tasks where the entanglement-assisted protocol using one-bit communication proves to be advantageous over classical communication. Finally, by constructing an explicit class of communication tasks, we show that a non-maximally entangled states outperform the maximally entangled state as a pre-shared resource between the communicating parties.

quant-pharXiv:2603.19105•Mar 20, 2026•0 citations

Unconditional quantum magic advantage in shallow circuit computation

Xingjian Zhang, Zhaokai Pan, Guoding Liu

Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of “magic” states—the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality—quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation. "Magic” is a resource in quantum computation that is believed to be important for quantum speedup, but the proofs of this have involved complexity assumptions or invoking a black-box oracle. Here, by constructing magic-required quantum pseudo-telepathy and converting it into a relation problem, the authors show an unconditional separation between constant-depth quantum circuits and magic-free ones.

arXiv:2402.12246•Nature Communications•Dec 3, 2024•4 citations

Experimental demonstration of quantum advantage in communication complexity for Euclidean distance problem

Verena Yacoub, Niraj Kumar, Iordanis Kerenidis +1 more

When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of $10^8$, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.

quant-pharXiv:2605.31516•Jun 1, 2026•0 citations

Om den lokala och icke-lokala strukturen hos magic

Partos, Alma

The purpose of this thesis is to investigate the behavior of quantum magic in many-body systems. According to the Gottesman-Knill theorem, the particular class of quantum states referred to as stabilizer states can be efficiently simulated on a classical computer. The property of non-stabilizerness, or magic, can be broadly defined as the distance between a general state and a stabilizer state, serving as a measure of classical hardness as well as a resource for quantum computation. Numerical studies of this property, as a feature of many-body systems, are classically hard. This work uses a combination of quantum circuit simulations and tensor-network methods to study the spread and characteristic features of magic in quantum systems. We demonstrate that this can be done with relative efficiency, while addressing questions about the characterization of non-local magic and its relation to quantum computational complexity.

•Jan 1, 2025•0 citations
Quantum systems are known to offer advantages over their classical counterpart in communication complexity protocols, where the aim is to minimize the amount of information exchange between distant parties to compute global functions of their distributed inputs. In this work, we establish that any one-way communication protocol implemented using a prime-dimensional quantum system -- restricted to stabilizer-state encodings and Clifford-operation decodings -- can be exactly simulated by transmitting a classical system of the same dimension, given access to shared randomness between the sender and receiver. In direct analogy with the Gottesman-Knill theorem, which attributes quantum computational speedup to non-stabilizer resources, commonly known as the magic resources, our result identifies the same non-stabilizer resources as the essential ingredient for the quantum advantage in one-way communication complexity. Furthermore, we present explicit tasks where even a 'minimal magic resource' suffices to achieve a provable quantum advantage, highlighting its efficient use in communication protocols.
From both intuitive and physical perspectives, it is generally recognized that within a resource theory framework, free operations cannot broadcast a resource state due to their inability to generate resource from free states. In the stabilizer formalism of fault-tolerant quantum computation, the basic ingredients of the corresponding resource theory consist of stabilizer states as free states and stabilizer operations as free operations. The celebrated Gottesman-Knill theorem shows that quantum advantages over classical computation come from the magic (nonstabilizer) resource, such as magic states or non-Clifford gates. In this work, we prove that broadcasting of any magic state via stabilizer operations is impossible, which is reminiscent of the no-broadcasting theorems for noncommuting states or quantum correlations. We further derive a trade-off relation between the magic resource consumed in the initial system and that gained in the target system. These results characterize magic states in the stabilizer formalism from the broadcasting angle, and may have implications for distributed quantum computation and quantum secret sharing.
Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks—the random access codes, equality problems defined by graphs, and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication presenting explicit protocols and utilizing semidefinite programming methods. In particular, we demonstrate for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values. Published by the American Physical Society 2024
We investigate the quantum advantage that can arise in typical two-party communication scenarios, where the sender and the receiver are allowed to share prior correlations. Focusing on communication tasks constrained by the distinguishability of the sender's inputs, we demonstrate that entanglement-assisted communication with both classical and quantum message can outperform classical communication supplemented with shared randomness. We begin by developing a general framework for communication tasks with pre-shared correlations. Within this framework, we establish an equivalence among entanglement-assisted classical communication, entanglement-assisted quantum communication, and quantum communication, showing that no hierarchy exists between these three paradigms. We then investigate the scenario where the receiver has no input and prove that no advantage can arise in this case. However, an advantage in the entanglement-assisted setting emerges once additional constraints are imposed on the dimension of the communicated message. This further highlights the superiority of entanglement-assisted classical communication over standard quantum communication. Then we demonstrate several tasks where the entanglement-assisted protocol using one-bit communication proves to be advantageous over classical communication. Finally, by constructing an explicit class of communication tasks, we show that a non-maximally entangled states outperform the maximally entangled state as a pre-shared resource between the communicating parties.
Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of “magic” states—the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality—quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation. "Magic” is a resource in quantum computation that is believed to be important for quantum speedup, but the proofs of this have involved complexity assumptions or invoking a black-box oracle. Here, by constructing magic-required quantum pseudo-telepathy and converting it into a relation problem, the authors show an unconditional separation between constant-depth quantum circuits and magic-free ones.
When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of 10810^8108, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.
The purpose of this thesis is to investigate the behavior of quantum magic in many-body systems. According to the Gottesman-Knill theorem, the particular class of quantum states referred to as stabilizer states can be efficiently simulated on a classical computer. The property of non-stabilizerness, or magic, can be broadly defined as the distance between a general state and a stabilizer state, serving as a measure of classical hardness as well as a resource for quantum computation. Numerical studies of this property, as a feature of many-body systems, are classically hard. This work uses a combination of quantum circuit simulations and tensor-network methods to study the spread and characteristic features of magic in quantum systems. We demonstrate that this can be done with relative efficiency, while addressing questions about the characterization of non-local magic and its relation to quantum computational complexity.