The Programme Committee of TQC 2024 selected 92 out of 460 submissions for a contributed talk (20% acceptance rate).
You may find the contributed talks here.
The list of accepted posters will be published on the 2nd of May, after the poster notification date. The conference schedule will be published in July.
Note on the list: The talks are listed in alphabetical order of title. Later they will be listed by day of presentation. The topic tags were self-selected by the authors upon submission, given the options provided by the PC chairs.
1.
Dmitry Grinko, Adam Burchardt, Maris Ozols
Efficient quantum circuits for port-based teleportation Talk
2024.
Abstract | Tags: Other, Quantum algorithms, Quantum communication, Quantum estimation and measurement, Quantum information theory
@Talk{T24_403,
title = {Efficient quantum circuits for port-based teleportation},
author = {Dmitry Grinko and Adam Burchardt and Maris Ozols},
year = {2024},
date = {2024-01-01},
abstract = {Port-based teleportation (PBT) is a variant of quantum teleportation that, unlike the canonical protocol by Bennett et al., does not require a correction operation on the teleported state. Since its introduction by Ishizaka and Hiroshima in 2008, no efficient implementation of PBT was known. We close this long-standing gap using methods from representation theory, in particular, recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We describe efficient quantum circuits for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We provide two constructions based on different encodings of the so-called Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(n log(n)) space complexity, and a Yamanouchi encoding that achieves O(n^2) time and O(log(n)) space complexity, both for constant local dimension and target error. We also describe efficient circuits for preparing the optimal resource states.},
keywords = {Other, Quantum algorithms, Quantum communication, Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Port-based teleportation (PBT) is a variant of quantum teleportation that, unlike the canonical protocol by Bennett et al., does not require a correction operation on the teleported state. Since its introduction by Ishizaka and Hiroshima in 2008, no efficient implementation of PBT was known. We close this long-standing gap using methods from representation theory, in particular, recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We describe efficient quantum circuits for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We provide two constructions based on different encodings of the so-called Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(n log(n)) space complexity, and a Yamanouchi encoding that achieves O(n^2) time and O(log(n)) space complexity, both for constant local dimension and target error. We also describe efficient circuits for preparing the optimal resource states.
2.
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
On the Power of Quantum Distributed Proofs Talk
2024.
Abstract | Tags: Quantum algorithms, Quantum communication, Quantum complexity theory
@Talk{T24_132,
title = {On the Power of Quantum Distributed Proofs},
author = {Atsuya Hasegawa and Srijita Kundu and Harumichi Nishimura},
year = {2024},
date = {2024-01-01},
abstract = {Quantum nondeterministic distributed computing was recently introduced as $mathsfdQMA$ (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In $mathsfdQMA$ protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al.~showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical or not. In this paper, we further investigate and characterize the power of the $mathsfdQMA$ protocols for various decision problems. First, we give a more efficient $mathsfdQMA$ protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient $mathsfdQMA$ protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication complexity protocols. Third, in a line network, we construct an efficient $mathsfdQMA$ protocol for a problem that has an efficient two-party $mathsfQMA$ communication complexity protocol. Finally, we obtain the first lower bounds on the proof and communication cost of $mathsfdQMA$ protocols. To prove a lower bound on the equality problem, we show any $mathsfdQMA$ protocol with an entangled proof between nodes can be simulated with a $mathsfdQMA$ protocol with a separable proof between nodes by using a $mathsfQMA$ communication-complete problem introduced by Raz and Shpilka (CCC 2004).},
keywords = {Quantum algorithms, Quantum communication, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
Quantum nondeterministic distributed computing was recently introduced as $mathsfdQMA$ (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In $mathsfdQMA$ protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al.~showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical or not. In this paper, we further investigate and characterize the power of the $mathsfdQMA$ protocols for various decision problems. First, we give a more efficient $mathsfdQMA$ protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient $mathsfdQMA$ protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication complexity protocols. Third, in a line network, we construct an efficient $mathsfdQMA$ protocol for a problem that has an efficient two-party $mathsfQMA$ communication complexity protocol. Finally, we obtain the first lower bounds on the proof and communication cost of $mathsfdQMA$ protocols. To prove a lower bound on the equality problem, we show any $mathsfdQMA$ protocol with an entangled proof between nodes can be simulated with a $mathsfdQMA$ protocol with a separable proof between nodes by using a $mathsfQMA$ communication-complete problem introduced by Raz and Shpilka (CCC 2004).
3.
Uma Girish, Srinivasan Arunachalam, Noam Lifshitz
One Clean Qubit Suffices for Quantum Communication Advantage Talk
2024.
Abstract | Tags: Models of quantum computation, Quantum algorithms, Quantum communication, Quantum complexity theory
@Talk{T24_30,
title = {One Clean Qubit Suffices for Quantum Communication Advantage},
author = {Uma Girish and Srinivasan Arunachalam and Noam Lifshitz},
year = {2024},
date = {2024-01-01},
abstract = {We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.},
keywords = {Models of quantum computation, Quantum algorithms, Quantum communication, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.
4.
Francesco Anna Mele, Farzin Salek, Vittorio Giovannetti, Ludovico Lami
Quantum communication on the bosonic loss-dephasing channel Talk
2024.
Abstract | Tags: Quantum communication, Quantum information theory
@Talk{T24_47,
title = {Quantum communication on the bosonic loss-dephasing channel},
author = {Francesco Anna Mele and Farzin Salek and Vittorio Giovannetti and Ludovico Lami},
year = {2024},
date = {2024-01-01},
abstract = {Quantum optical systems are typically affected by two types of noise: photon loss and dephasing. Despite extensive research on each noise process individually, a comprehensive understanding of their combined effect is still lacking. A crucial problem lies in determining the values of loss and dephasing for which the resulting loss-dephasing channel is anti-degradable, implying the absence of codes capable of correcting its effect or, alternatively, capable of enabling quantum communication. A conjecture in [Quantum 6, 821 (2022)] suggested that the bosonic loss-dephasing channel is anti-degradable if and only if the loss is above 50%. In this paper we refute this conjecture, specifically proving that for any value of the loss, if the dephasing is above a critical value, then the bosonic loss-dephasing channel is anti-degradable. While our result identifies a large parameter region where quantum communication is not possible, we also prove that if two-way classical communication is available, then quantum communication — and thus quantum key distribution — is always achievable, even for high values of loss and dephasing.},
keywords = {Quantum communication, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
Quantum optical systems are typically affected by two types of noise: photon loss and dephasing. Despite extensive research on each noise process individually, a comprehensive understanding of their combined effect is still lacking. A crucial problem lies in determining the values of loss and dephasing for which the resulting loss-dephasing channel is anti-degradable, implying the absence of codes capable of correcting its effect or, alternatively, capable of enabling quantum communication. A conjecture in [Quantum 6, 821 (2022)] suggested that the bosonic loss-dephasing channel is anti-degradable if and only if the loss is above 50%. In this paper we refute this conjecture, specifically proving that for any value of the loss, if the dephasing is above a critical value, then the bosonic loss-dephasing channel is anti-degradable. While our result identifies a large parameter region where quantum communication is not possible, we also prove that if two-way classical communication is available, then quantum communication — and thus quantum key distribution — is always achievable, even for high values of loss and dephasing.
5.
Niklas Galke, Lauritz Luijk, Henrik Wilming
Sufficiency of Rényi divergences Talk
2024.
Abstract | Tags: Quantum communication, Quantum information theory
@Talk{T24_343,
title = {Sufficiency of Rényi divergences},
author = {Niklas Galke and Lauritz Luijk and Henrik Wilming},
year = {2024},
date = {2024-01-01},
abstract = {A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.},
keywords = {Quantum communication, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.
