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:quant-ph/0507270

Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks

Harumichi Nishimura, Tomoyuki Yamakami

Published Jul 28, 2005• 0 citations
arXivHTMLPDF

Abstract

Two-party one-way quantum communication has been extensively studied in the recent literature. We target the size of minimal information that is necessary for a feasible party to finish a given combinatorial task, such as distinction of instances, using one-way communication from another party. This type of complexity measure has been studied under various names: advice complexity, Kolmogorov complexity, distinguishing complexity, and instance complexity. We present a general framework focusing on underlying combinatorial takes to study these complexity measures using quantum information processing. We introduce the key notions of relative hardness and quantum advantage, which provide the foundations for task-based quantum minimal one-way information complexity theory.

DOI
10.48550/arxiv.quant-ph/0507270

Related papers

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•14 citations

Formal Framework for Quantum Advantage

Harry Buhrman, Niklas Galke, Konstantinos Meichanetzidis

Motivated by notions of quantum heuristics and by average-case rather than worst-case algorithmic analysis, we define quantum computational advantage in terms of individual problem instances. Inspired by the classical notions of Kolmogorov complexity and instance complexity, we define their quantum versions. This allows us to define queasy instances of computational problems, like e.g. Satisfiability and Factoring, as those whose quantum instance complexity is significantly smaller than their classical instance complexity. These instances indicate quantum advantage: they are easy to solve on a quantum computer, but classical algorithms struggle (they feel queasy). Via a reduction from Factoring, we prove the existence of queasy Satisfiability instances; specifically, these instances are maximally queasy (under reasonable complexity-theoretic assumptions). Further, we show that there is exponential algorithmic utility in the queasiness of a quantum algorithm. This formal framework serves as a beacon that guides the hunt for quantum advantage in practice, and moreover, because its focus lies on single instances, it can lead to new ways of designing quantum algorithms.

arXiv:2510.01953•Oct 2, 2025•9 citations

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).

arXiv:quant-ph/0402095•Theory of Computing•Jan 1, 2005•157 citations

Direct information lower bounds for one-way communication complexity problems: Applications to the demonstration of an unconditional quantum advantage and to cryptography (Short Paper)

Romain Alléaume, Gabriel Blanchot, Philippe Gaborit +1 more

Information cost is often treated as a secondary quantity in communication complexity, even when the operational resource of interest is the information revealed by a protocol rather than its message length. This mismatch becomes particularly important in quantum communication and cryptography, where classical leakage must be compared directly with the information carried by quantum states. For this reason, we derive direct finite-size lower bounds, with explicit constants, on the information cost of one-way private-coin protocols for Hidden Matching, a communication-complexity problem, and two related tasks: Sampling Matching and Beta-Partial Matching. These bounds lead to two concrete applications. First, they provide a universal classical benchmark for coherent-state implementations of Sampling Matching, opening a route to an unconditional quantum advantage in information cost for a one-way communication complexity problem on a photonic platform. Second, they substantially tighten the analysis of HM-QCT, a recent everlastingly secure hybrid post-quantum/QKD protocol, bringing its implementation closer to realistic optical parameters while preserving the possibility of exceeding the fundamental rate-loss limits of standard QKD.

ACM Conference on Post-Quantum and Quantum-based Security•Oct 26, 2026•0 citations

Limitations of quantum advice and one-way communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.

IEEE Conference on Computational Complexity (CCC)•Nov 12, 2004•34 citations

Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication

Philippe Allard Guérin, Adrien Feix, Mateus Araújo +1 more

In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.

arXiv:1605.07372•Physical Review Letters•Sep 1, 2016•239 citations
Two-party one-way quantum communication has been extensively studied in the recent literature. We target the size of minimal information that is necessary for a feasible party to finish a given combinatorial task, such as distinction of instances, using one-way communication from another party. This type of complexity measure has been studied under various names: advice complexity, Kolmogorov complexity, distinguishing complexity, and instance complexity. We present a general framework focusing on underlying combinatorial takes to study these complexity measures using quantum information processing. We introduce the key notions of relative hardness and quantum advantage, which provide the foundations for task-based quantum minimal one-way information complexity theory.
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
Motivated by notions of quantum heuristics and by average-case rather than worst-case algorithmic analysis, we define quantum computational advantage in terms of individual problem instances. Inspired by the classical notions of Kolmogorov complexity and instance complexity, we define their quantum versions. This allows us to define queasy instances of computational problems, like e.g. Satisfiability and Factoring, as those whose quantum instance complexity is significantly smaller than their classical instance complexity. These instances indicate quantum advantage: they are easy to solve on a quantum computer, but classical algorithms struggle (they feel queasy). Via a reduction from Factoring, we prove the existence of queasy Satisfiability instances; specifically, these instances are maximally queasy (under reasonable complexity-theoretic assumptions). Further, we show that there is exponential algorithmic utility in the queasiness of a quantum algorithm. This formal framework serves as a beacon that guides the hunt for quantum advantage in practice, and moreover, because its focus lies on single instances, it can lead to new ways of designing quantum algorithms.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}BQP/qpoly⊆PP/poly, where BQP/qpoly\mathsf{BQP/qpoly}BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊄BQP/qpoly\mathsf{NP}\not \subset \mathsf{BQP/qpoly}NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).
Information cost is often treated as a secondary quantity in communication complexity, even when the operational resource of interest is the information revealed by a protocol rather than its message length. This mismatch becomes particularly important in quantum communication and cryptography, where classical leakage must be compared directly with the information carried by quantum states. For this reason, we derive direct finite-size lower bounds, with explicit constants, on the information cost of one-way private-coin protocols for Hidden Matching, a communication-complexity problem, and two related tasks: Sampling Matching and Beta-Partial Matching. These bounds lead to two concrete applications. First, they provide a universal classical benchmark for coherent-state implementations of Sampling Matching, opening a route to an unconditional quantum advantage in information cost for a one-way communication complexity problem on a photonic platform. Second, they substantially tighten the analysis of HM-QCT, a recent everlastingly secure hybrid post-quantum/QKD protocol, bringing its implementation closer to realistic optical parameters while preserving the possibility of exceeding the fundamental rate-loss limits of standard QKD.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.