It is well known that the Helstrom bound can be improved by generalizing the form of a coherent state. Thus, designing a quantum measurement achieving the improved Helstrom bound is important for novel quantum communication. In this paper, we analytically show that the improved Helstrom bound can be achieved by a projective measurement composed of orthogonal non-standard Schrödinger cat states. Moreover, we numerically show that the improved Helstrom bound can be nearly achieved by an indirect measurement based on the Jaynes–Cummings model. As the Jaynes–Cummings model describes an interaction between a light and a two-level atom, we emphasize that the indirect measurement considered in this paper has potential to be experimentally implemented.It is well known that the Helstrom bound can be improved by generalizing the form of a coherent state. Thus, designing a quantum measurement achieving the improved Helstrom bound is important for novel quantum communication. In this paper, we analytically show that the improved Helstrom bound can be achieved by a projective measurement composed of orthogonal non-standard Schrödinger cat states. Moreover, we numerically show that the improved Helstrom bound can be nearly achieved by an indirect measurement based on the Jaynes–Cummings model. As the Jaynes–Cummings model describes an interaction between a light and a two-level atom, we emphasize that the indirect measurement considered in this paper has potential to be experimentally implemented.

arXiv:2112.02312Journal of the Optical Society of America BFeb 28, 20222 citations

Upper Bounds on Communication in Terms of Approximate Rank

Anna Gál, Ridwan Syed

Theory of Computing SystemsDec 12, 20233 citations

Towards Optimal Non-interactive Secure Multiparty Computation for Abelian Programs

Maki Yoshida

Non-interactive secure multiparty computation is a method to share and compute a private function $f$ among $n$ parties holding private inputs xi with 1 $n$ in the information theoretical setting. Each party locally computes a message from a share of $f$ and send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keeping $f$ and xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.Non-interactive secure multiparty computation is a method to share and compute a private function$f$among$n$parties holding private inputs xi with 1$n$in the information theoretical setting. Each party locally computes a message from a share of$f$and send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keeping$f$and xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.

IEEE International Symposium on Information Theory (ISIT)Jul 7, 20240 citations

Upper Bounds on Communication in Terms of Approximate Rank

Anna Gál, Ridwan Syed

Lecture notes in computer scienceJan 1, 20214 citations

A New Protocol for Asymmetric Communication Channels: Reaching the Lower Bounds

S Ghazizadeh, Mohammad Ghodsi, Ali Saberi

Scientia IranicaJan 1, 200111 citations

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Chengu Wang

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$ . Alice holds a unit vector $u$ and Bob holds an $n/2$ -dimensional subspace $H$ ; they must distinguish $u\in H$ from $u\in H^\perp$ . An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

cs.CCCross-listedarXiv:2610.30052Oct 22, 20260 citations

Non-interactive secure multiparty computation is a method to share and compute a private function

f

among

n

parties holding private inputs xi with 1

n

in the information theoretical setting. Each party locally computes a message from a share of

f

and send it to a referee in parallel. The referee obtains the output f (xi,… , xn) while keeping

f

and xi private other than what can be inferred from the output. The communication complexity is evaluated by the maximum length of shares and messages. In the previous work, several kinds of function families, upper and lower bounds have been improved and the only gaps remaining are for the group products and the Abelian programs (including symmetric functions). This paper improves the communication complexity of both function families towards the optimum by deriving a new lower bound for the group products that matches the previous upper bound (up to a constant factor) and the first asymptotically optimal upper bound for the Abelian programs.

We prove that the randomized communication complexity of Vector-in-Subspace in

\mathbb R^n

with error at most

1/3

Θ(\sqrt n)

. Alice holds a unit vector

u

and Bob holds an

n/2

-dimensional subspace

H

; they must distinguish

u\in H

from

u\in H^\perp

. An exact one-way quantum protocol uses

O(\log n)

qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's

O(\sqrt n)

upper bound, improves the

Ω(n^{1/3})

lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's

Ω(\sqrt n)

result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.