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.
Kuo-Chin Chen, Simon Apers, Min-Hsiu Hsieh
(Quantum) complexity of testing signed graph clusterability Talk
2024.
Abstract | Tags: Other, Proceedings, Quantum algorithms
@Talk{T24_234,
title = {(Quantum) complexity of testing signed graph clusterability},
author = {Kuo-Chin Chen and Simon Apers and Min-Hsiu Hsieh},
year = {2024},
date = {2024-01-01},
abstract = {This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $tildeO(N^1/3)$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an $tildeØmega(sqrtN)$ classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.},
keywords = {Other, Proceedings, Quantum algorithms},
pubstate = {published},
tppubtype = {Talk}
}
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $tildeO(N^1/3)$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an $tildeØmega(sqrtN)$ classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
2.
David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games Talk
2024.
Abstract | Tags: Other, Quantum complexity theory, Quantum cryptography
@Talk{T24_235,
title = {A Computational Tsirelson's Theorem for the Value of Compiled XOR Games},
author = {David Cui and Giulio Malavolta and Arthur Mehta and Anand Natarajan and Connor Paddock and Simon Schmidt and Michael Walter and Tina Zhang},
year = {2024},
date = {2024-01-01},
abstract = {Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a "nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.},
keywords = {Other, Quantum complexity theory, Quantum cryptography},
pubstate = {published},
tppubtype = {Talk}
}
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a "nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.
3.
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.
4.
Sergey Bravyi, Natalie Parham, Minh Tran
Identity check problem for shallow quantum circuits Talk
2024.
Abstract | Tags: Other, Quantum information theory, Simulation of quantum systems
@Talk{T24_233,
title = {Identity check problem for shallow quantum circuits},
author = {Sergey Bravyi and Natalie Parham and Minh Tran},
year = {2024},
date = {2024-01-01},
abstract = {Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $alpha=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $|U-I|$ can be efficiently approximated within a factor $alpha=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $alpha=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.},
keywords = {Other, Quantum information theory, Simulation of quantum systems},
pubstate = {published},
tppubtype = {Talk}
}
Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $alpha=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $|U-I|$ can be efficiently approximated within a factor $alpha=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $alpha=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.
5.
Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck Franca, Yihui Quek
Noise-induced shallow circuits and absence of barren plateaus Talk
2024.
Abstract | Tags: Intersection of quantum information and machine learning, Other, Quantum complexity theory, Simulation of quantum systems
@Talk{T24_409,
title = {Noise-induced shallow circuits and absence of barren plateaus},
author = {Antonio Anna Mele and Armando Angrisani and Soumik Ghosh and Sumeet Khatri and Jens Eisert and Daniel Stilck Franca and Yihui Quek},
year = {2024},
date = {2024-01-01},
abstract = {We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.},
keywords = {Intersection of quantum information and machine learning, Other, Quantum complexity theory, Simulation of quantum systems},
pubstate = {published},
tppubtype = {Talk}
}
We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.
6.
Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel, Jordi Weggemans
Permutation tests for quantum state identity Talk
2024.
Abstract | Tags: Other, Quantum estimation and measurement, Quantum information theory
@Talk{T24_400,
title = {Permutation tests for quantum state identity},
author = {Harry Buhrman and Dmitry Grinko and Philip Verduyn Lunel and Jordi Weggemans},
year = {2024},
date = {2024-01-01},
abstract = {The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether n unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of (fine-grained formulations of) the quantum state identity problem. Using tools from semi-definite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general G-test which uses an arbitrary subgroup G of S_n, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n-1 Swap tests.},
keywords = {Other, Quantum estimation and measurement, Quantum information theory},
pubstate = {published},
tppubtype = {Talk}
}
The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether n unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of (fine-grained formulations of) the quantum state identity problem. Using tools from semi-definite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general G-test which uses an arbitrary subgroup G of S_n, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n-1 Swap tests.
7.
Junqiao Lin
Tracial embeddable strategies: Lifting MIP* tricks to MIPco Talk
2024.
Abstract | Tags: Models of quantum computation, Other, Quantum complexity theory
@Talk{T24_130,
title = {Tracial embeddable strategies: Lifting MIP* tricks to MIPco},
author = {Junqiao Lin},
year = {2024},
date = {2024-01-01},
abstract = {We prove that any two-party correlation in the commuting operator model can be approximated using a tracial embeddable strategy, a class of strategy defined on a finite tracial von Neumann algebra, which we define in this paper. Using this characterization, we show that any approximately synchronous correlation can be approximated to the average of a collection of synchronous correlations in the commuting operator model. This generalizes the result from Vidick [JMP 2022] which only applies to finite-dimensional quantum correlations. As a corollary, we show that the quantum tensor code test from Ji et al. [FOCS 2022] follows the soundness property even under the general commuting operator model. Furthermore, we extend the state-dependent norm variant of the Gowers-Hatami theorem to finite von Neumann algebras. Combined with the aforementioned characterization, this enables us to lift many known results about robust self-testing for non-local games to the commuting operator model, including a sample efficient finite-dimensional EPR testing for the commuting operator strategies. We believe that, in addition to the contribution from this paper, this class of strategies can be helpful for further understanding non-local games in the infinite-dimensional setting.},
keywords = {Models of quantum computation, Other, Quantum complexity theory},
pubstate = {published},
tppubtype = {Talk}
}
We prove that any two-party correlation in the commuting operator model can be approximated using a tracial embeddable strategy, a class of strategy defined on a finite tracial von Neumann algebra, which we define in this paper. Using this characterization, we show that any approximately synchronous correlation can be approximated to the average of a collection of synchronous correlations in the commuting operator model. This generalizes the result from Vidick [JMP 2022] which only applies to finite-dimensional quantum correlations. As a corollary, we show that the quantum tensor code test from Ji et al. [FOCS 2022] follows the soundness property even under the general commuting operator model. Furthermore, we extend the state-dependent norm variant of the Gowers-Hatami theorem to finite von Neumann algebras. Combined with the aforementioned characterization, this enables us to lift many known results about robust self-testing for non-local games to the commuting operator model, including a sample efficient finite-dimensional EPR testing for the commuting operator strategies. We believe that, in addition to the contribution from this paper, this class of strategies can be helpful for further understanding non-local games in the infinite-dimensional setting.
