6 papers
Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
Daiki Suruga
Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on qua…
Zero-error expectation equals amortized query complexity
Daiki Suruga
This paper investigates the direct sum question for expected randomized and distributional query complexity. Our main result gives an exact characterization of the amortized expect…
Zero-error information equals amortized communication complexity
Daiki Suruga
The direct sum problem in computational complexity asks whether solving independent instances of a computational task inherently requires times the resources needed to solv…
Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
Daiki Suruga
Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown…
Direct sum theorems beyond query complexity
Daiki Suruga
A fundamental question in computer science is: Is it harder to solve instances independently than to solve them simultaneously? This question, known as the direct sum question…
A probabilistic analysis on general probabilistic scheduling problems
Daiki Suruga
The scheduling problem is a key class of optimization problems and has various kinds of applications both in practical and theoretical scenarios. In the scheduling problem, probabi…