4 papers
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…