Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model. Recently, Coiteux-Roy~et~al.~(STOC 2024) showed that quantum resources do not help for 3-coloring \textit{unrooted} trees: in particular, their lower bound holds in the stronger \textit{non-signaling} model, which formalizes the principle of physical causality in distributed computing. The case of \textit{rooted} trees, however, was left open by their work. For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors $n$ -node trees in $O(\log^\star n)$ rounds, matching Linial's classical $Ω(\log^\star n)$ lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors $n$ -node rooted trees with probability at least ${1-O(1/\log n)}$ must perform $Ω(\log^\star n)$ rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of $Ω(\log^\star Δ)$ for 3-coloring any $Δ$ -ary tree with success probability at least $1-1/Δ$ . The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument. We also show, as a separate result, that 2-coloring even-length $n$ -node cycles with probability $1-O(1/n)$ requires $n/2-1$ rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known $\lceil (n-2)/4 \rceil$ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model. Recently, Coiteux-Roy~et~al.~(STOC 2024) showed that quantum resources do not help for 3-coloring \textit{unrooted} trees: in particular, their lower bound holds in the stronger \textit{non-signaling} model, which formalizes the principle of physical causality in distributed computing. The case of \textit{rooted} trees, however, was left open by their work. For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors $n$-node trees in $O(\log^\star n)$ rounds, matching Linial's classical $Ω(\log^\star n)$ lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors $n$-node rooted trees with probability at least ${1-O(1/\log n)}$ must perform $Ω(\log^\star n)$ rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of $Ω(\log^\star Δ)$ for 3-coloring any $Δ$-ary tree with success probability at least $1-1/Δ$. The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument. We also show, as a separate result, that 2-coloring even-length $n$-node cycles with probability $1-O(1/n)$ requires $n/2-1$ rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known $\lceil (n-2)/4 \rceil$ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.

cs.DCCross-listedarXiv:2607.04852Jul 7, 20260 citations

Classical Gates and Algorithms

Belal Ehsan Baaquie, L. C. Kwek

Springer eBooksJan 1, 20230 citations

Low-depth parallelization of k-local gates and applications

Bryan O’Gorman, William Huggins, Eleanor Gilbert Rieffel +1 more

Bulletin of the American Physical SocietyMar 8, 20190 citations

Quantum networks for implementing effiently a nonlocal N-qubit controlled unitary gate via non-symmetric quantum channels: Designing and optimizing

Libing Chen, Hong LU

We show how a nonlocal N-qubit controlled unitary gate can be implemented locally and effectively by using non-symmetric quantum channels. We construct respectively two quantum networks for realizing conclusively this nonlocal quantum gate. The first one hires (N–2) symmetric qubit-qubit Bell states and a non-symmetric qubit-qudit Bell state as quantum channels. The basic idea of this scheme is to use (N–2) additional levels of this qudit to “hide” certain computational states of (N–1) nonlocal control states from the conditional dynamics, which results in an effective nonlocal N-qubit controlled unitary gate design. In this scheme, however, either the number of the additional levels or that of 1-qudit gates needs to increase with N. The other one can improve significantly the local implementation of this nonlocal gate if we harness (N–1) non-symmetric qubit-qutrit Bell states as quantum channels. This scheme uses respectively (N–1) qutrits’s additional levels to expose one and only one initial computational state of (N–1) nonlocal control states to the conditional dynamics. In comparison with the first one, the procedure is greatly simplified, and the total gate time is reduced. The fact that the quantum network that does the proposed implementation is built entirely of local single-body and two-body gates, and has only (3N–4) two-body gates is notable.We show how a nonlocal N-qubit controlled unitary gate can be implemented locally and effectively by using non-symmetric quantum channels. We construct respectively two quantum networks for realizing conclusively this nonlocal quantum gate. The first one hires (N–2) symmetric qubit-qubit Bell states and a non-symmetric qubit-qudit Bell state as quantum channels. The basic idea of this scheme is to use (N–2) additional levels of this qudit to “hide” certain computational states of (N–1) nonlocal control states from the conditional dynamics, which results in an effective nonlocal N-qubit controlled unitary gate design. In this scheme, however, either the number of the additional levels or that of 1-qudit gates needs to increase with N. The other one can improve significantly the local implementation of this nonlocal gate if we harness (N–1) non-symmetric qubit-qutrit Bell states as quantum channels. This scheme uses respectively (N–1) qutrits’s additional levels to expose one and only one initial computational state of (N–1) nonlocal control states to the conditional dynamics. In comparison with the first one, the procedure is greatly simplified, and the total gate time is reduced. The fact that the quantum network that does the proposed implementation is built entirely of local single-body and two-body gates, and has only (3N–4) two-body gates is notable.

Zhongguo kexue. Wulixue Lixue TianwenxueJul 21, 20172 citations

Congestion-free Multiflow Quantum Tree Network with Logarithmic Overhead

Hyeongrak Choi, Marc Grau Davis, Dirk Englund

We propose quantum tree network (QTN) designs that are 1) free from congestion in multiflow communications, 2) optimal routing with only local information (self-information) and 3) completely covers 2D surface, 4) with only logarithmic overhead. If the channel is dominated by the insertion loss and the communication is limited by the local gates, as in current state-of-the-art technologies, the overhead is log(N), while this is relaxed to the general cases with poly-log overhead by engaging repeater chains in the long range communication.We propose quantum tree network (QTN) designs that are 1) free from congestion in multiflow communications, 2) optimal routing with only local information (self-information) and 3) completely covers 2D surface, 4) with only logarithmic overhead. If the channel is dominated by the insertion loss and the communication is limited by the local gates, as in current state-of-the-art technologies, the overhead is log(N), while this is relaxed to the general cases with poly-log overhead by engaging repeater chains in the long range communication.

IEEE/ACM Symposium on Edge Computing (SEC)Dec 1, 20221 citation

Finding Optimal Implementations of Non-native CNOT Gates Using SAT

Philipp Niemann, L.O. Muller, Rolf Drechsler

Lecture notes in computer scienceJan 1, 20212 citations

n

-node trees in

O(\log^\star n)

rounds, matching Linial's classical

Ω(\log^\star n)

lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors

n

-node rooted trees with probability at least

{1-O(1/\log n)}

must perform

Ω(\log^\star n)

rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of

Ω(\log^\star Δ)

for 3-coloring any

Δ

-ary tree with success probability at least

1-1/Δ

. The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument. We also show, as a separate result, that 2-coloring even-length

n

-node cycles with probability

1-O(1/n)

requires

n/2-1

rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known

\lceil (n-2)/4 \rceil

lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.