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 conference schedule is now published.
How to change talk slots: If you are giving a talk and would like to change your scheduled slot, contact the authors of another talk to swap, and write to the organizers only when you have a swap arrangement. You may use the Discord server to ask if anyone is willing to swap. Please try to swap with a talk from the same field, so that sessions can remain thematic and audience members don’t need to move rooms in the middle of a session.
1.
Kuo-Chin Chen, Simon Apers, Min-Hsiu Hsieh
(Quantum) complexity of testing signed graph clusterability Talk
2024.
Abstract | Tags: Proceedings, Wednesday
@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 = {Proceedings, Wednesday},
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.
Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke
Classical Verification of Quantum Learning Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_26,
title = {Classical Verification of Quantum Learning},
author = {Matthias C. Caro and Marcel Hinsche and Marios Ioannou and Alexander Nietner and Ryan Sweke},
url = {https://arxiv.org/abs/2306.04843},
year = {2024},
date = {2024-01-01},
abstract = {Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.
3.
Wenhao He, Tongyang Li, Xiantao Li, Zecheng Li, Chunhao Wang, Ke Wang
Efficient Optimal Control of Open Quantum Systems Talk
2024.
Abstract | Tags: Proceedings, Wednesday
@Talk{T24_423,
title = {Efficient Optimal Control of Open Quantum Systems},
author = {Wenhao He and Tongyang Li and Xiantao Li and Zecheng Li and Chunhao Wang and Ke Wang},
year = {2024},
date = {2024-01-01},
abstract = {The optimal control problem for open quantum systems can be formulated as a time- dependent Lindbladian that is parameterized by a number of time-dependent control variables. Given an observable and an initial state, the goal is to tune the control variables so that the expected value of some observable with respect to the final state is maximized. In this paper, we present algorithms for solving this optimal control problem efficiently, i.e., having a poly-logarithmic dependency on the system dimension, which is exponentially faster than best-known classical algorithms. Our algorithms are hybrid, consisting of both quantum and classical components. The quantum procedure simulates time-dependent Lindblad evolution that drives the initial state to the final state, and it also provides access to the gradients of the objective function via quantum gradient estimation. The classical procedure uses the gradient information to update the control variables. At the technical level, we provide the first (to the best of our knowledge) simulation al- gorithm for time-dependent Lindbladians with an ℓ1-norm dependence. As an alternative, we also present a simulation algorithm in the interaction picture to improve the algorithm for the cases where the time-independent component of a Lindbladian dominates the time-dependent part. On the classical side, we heavily adapt the state-of-the-art classical optimization analysis to interface with the quantum part of our algorithms. Both the quantum simulation techniques and the classical optimization analyses might be of independent interest},
keywords = {Proceedings, Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
The optimal control problem for open quantum systems can be formulated as a time- dependent Lindbladian that is parameterized by a number of time-dependent control variables. Given an observable and an initial state, the goal is to tune the control variables so that the expected value of some observable with respect to the final state is maximized. In this paper, we present algorithms for solving this optimal control problem efficiently, i.e., having a poly-logarithmic dependency on the system dimension, which is exponentially faster than best-known classical algorithms. Our algorithms are hybrid, consisting of both quantum and classical components. The quantum procedure simulates time-dependent Lindblad evolution that drives the initial state to the final state, and it also provides access to the gradients of the objective function via quantum gradient estimation. The classical procedure uses the gradient information to update the control variables. At the technical level, we provide the first (to the best of our knowledge) simulation al- gorithm for time-dependent Lindbladians with an ℓ1-norm dependence. As an alternative, we also present a simulation algorithm in the interaction picture to improve the algorithm for the cases where the time-independent component of a Lindbladian dominates the time-dependent part. On the classical side, we heavily adapt the state-of-the-art classical optimization analysis to interface with the quantum part of our algorithms. Both the quantum simulation techniques and the classical optimization analyses might be of independent interest
4.
Nadine Meister, Christopher Pattison, John Preskill
Efficient soft-output decoders for the surface code Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_393,
title = {Efficient soft-output decoders for the surface code},
author = {Nadine Meister and Christopher Pattison and John Preskill},
url = {https://arxiv.org/abs/2405.07433},
year = {2024},
date = {2024-01-01},
abstract = {Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome (``soft-output decoders'') can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work, we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a ``hierarchical code,'' a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome (``soft-output decoders'') can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work, we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a ``hierarchical code,'' a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.
5.
Joshua Cudby, Sergii Strelchuk
Gaussian decomposition of magic states for matchgate computations Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_33,
title = {Gaussian decomposition of magic states for matchgate computations},
author = {Joshua Cudby and Sergii Strelchuk},
url = {https://arxiv.org/abs/2307.12654},
year = {2024},
date = {2024-01-01},
abstract = {Magic states, pivotal for universal quantum computation via classically simulable Clifford gates, often undergo decomposition into resourceless stabilizer states, facilitating simulation through classical means. This approach yields three operationally significant metrics: stabilizer rank, fidelity, and extent. We extend these simulation methods to encompass matchgate circuits (MGCs), and define equivalent metrics for this setting. We begin with an investigation into the algebraic constraints defining Gaussian states, marking the first explicit characterisation of these states. The explicit description of Gaussian states is pivotal to our methods for tackling all the simulation tasks. Central to our inquiry is the concept of Gaussian rank – a pivotal metric defining the minimum terms required for decomposing a quantum state into Gaussian constituents. This metric holds paramount significance in determining the runtime of rank-based simulations for MGCs featuring magic state inputs. The absence of low-rank decompositions presents a computational hurdle, thereby prompting a deeper examination of fermionic magic states. We find that the Gaussian rank of 2 instances of our canonical magic state is 4 under symmetry-restricted decompositions. Additionally, our numerical analysis suggests the absence of low-rank decompositions for 2 or 3 copies of this magic state. Further, we explore the Gaussian extent, a convex metric offering an upper bound on the rank. We prove the Gaussian extent's multiplicative behaviour on 4-qubit systems, along with initial strides towards proving its sub-multiplicative nature in general settings. One important result in that direction we present is an upper bound on the Gaussian fidelity of generic states.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Magic states, pivotal for universal quantum computation via classically simulable Clifford gates, often undergo decomposition into resourceless stabilizer states, facilitating simulation through classical means. This approach yields three operationally significant metrics: stabilizer rank, fidelity, and extent. We extend these simulation methods to encompass matchgate circuits (MGCs), and define equivalent metrics for this setting. We begin with an investigation into the algebraic constraints defining Gaussian states, marking the first explicit characterisation of these states. The explicit description of Gaussian states is pivotal to our methods for tackling all the simulation tasks. Central to our inquiry is the concept of Gaussian rank – a pivotal metric defining the minimum terms required for decomposing a quantum state into Gaussian constituents. This metric holds paramount significance in determining the runtime of rank-based simulations for MGCs featuring magic state inputs. The absence of low-rank decompositions presents a computational hurdle, thereby prompting a deeper examination of fermionic magic states. We find that the Gaussian rank of 2 instances of our canonical magic state is 4 under symmetry-restricted decompositions. Additionally, our numerical analysis suggests the absence of low-rank decompositions for 2 or 3 copies of this magic state. Further, we explore the Gaussian extent, a convex metric offering an upper bound on the rank. We prove the Gaussian extent's multiplicative behaviour on 4-qubit systems, along with initial strides towards proving its sub-multiplicative nature in general settings. One important result in that direction we present is an upper bound on the Gaussian fidelity of generic states.
6.
Shivan Mittal, Nicholas Hunter-Jones
Local random quantum circuits form approximate designs on arbitrary architectures Talk
2024.
@Talk{T24_309,
title = {Local random quantum circuits form approximate designs on arbitrary architectures},
author = {Shivan Mittal and Nicholas Hunter-Jones},
year = {2024},
date = {2024-01-01},
abstract = {We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.
7.
Allyson Silva, Xiangyi Zhang, Zachary Webb, Mia Kramer, Chan-Woo Yang, Xiao Liu, Jessica Lemieux, Kawai Chen, Artur Scherer, Pooya Ronagh
Multi-qubit Lattice Surgery Scheduling Talk
2024.
Abstract | Tags: Proceedings, Wednesday | Links:
@Talk{T24_426,
title = {Multi-qubit Lattice Surgery Scheduling},
author = {Allyson Silva and Xiangyi Zhang and Zachary Webb and Mia Kramer and Chan-Woo Yang and Xiao Liu and Jessica Lemieux and Kawai Chen and Artur Scherer and Pooya Ronagh},
url = {https://arxiv.org/abs/2405.17688},
year = {2024},
date = {2024-01-01},
abstract = {Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and application-inspired circuits demonstrates the method's scalability and performance. We show that the transpilation significantly reduces the circuit length on the set of circuits tested, and that the resulting circuit of multi-qubit gates has a further reduction in the expected circuit execution time compared to serial execution.},
keywords = {Proceedings, Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and application-inspired circuits demonstrates the method's scalability and performance. We show that the transpilation significantly reduces the circuit length on the set of circuits tested, and that the resulting circuit of multi-qubit gates has a further reduction in the expected circuit execution time compared to serial execution.
8.
Eric Culf, Arthur Mehta
New Approaches to Complexity via Quantum Graphs Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_123,
title = {New Approaches to Complexity via Quantum Graphs},
author = {Eric Culf and Arthur Mehta},
url = {https://arxiv.org/abs/2309.12887},
year = {2024},
date = {2024-01-01},
abstract = {Problems based on the structure of graphs – for example finding cliques, independent sets, or colourings – are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and consequently the connections between quantum graphs and complexity have been underexplored.
In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes NP, MA, QMA, and QMA(2). In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of QMA(k) to QMA(2) via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Problems based on the structure of graphs – for example finding cliques, independent sets, or colourings – are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and consequently the connections between quantum graphs and complexity have been underexplored.
In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes NP, MA, QMA, and QMA(2). In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of QMA(k) to QMA(2) via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.
In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes NP, MA, QMA, and QMA(2). In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of QMA(k) to QMA(2) via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.
9.
Xavier Coiteux-Roy, Francesco D'Amore, Rishikesh Gajjala, Fabian Kuhn, Francois Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela
No distributed quantum advantage for approximate graph coloring Talk
2024.
@Talk{T24_60,
title = {No distributed quantum advantage for approximate graph coloring},
author = {Xavier Coiteux-Roy and Francesco D'Amore and Rishikesh Gajjala and Fabian Kuhn and Francois Le Gall and Henrik Lievonen and Augusto Modanese and Marc-Olivier Renou and Gustav Schmid and Jukka Suomela},
year = {2024},
date = {2024-01-01},
abstract = {We give an almost complete characterization of the hardness of $c$-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a $c$-coloring in χ-chromatic graphs in $tildemathcalO(n^frac1alpha)$ rounds, with $alpha = biglłfloorfracc-1chi - 1bigrrfloor$. ıtem We prove that any distributed algorithm for this problem requires $Ømega(n^frac1alpha)$ rounds. endenumerate Our upper bound holds in the classical, deterministic $mathsfLOCAL$ model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic $mathsfLOCAL$ and randomized $mathsfLOCAL$ but also $mathsfquantum$-$mathsfLOCAL$, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
We give an almost complete characterization of the hardness of $c$-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a $c$-coloring in χ-chromatic graphs in $tildemathcalO(n^frac1alpha)$ rounds, with $alpha = biglłfloorfracc-1chi - 1bigrrfloor$. ıtem We prove that any distributed algorithm for this problem requires $Ømega(n^frac1alpha)$ rounds. endenumerate Our upper bound holds in the classical, deterministic $mathsfLOCAL$ model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic $mathsfLOCAL$ and randomized $mathsfLOCAL$ but also $mathsfquantum$-$mathsfLOCAL$, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.
10.
Tobias Haug, Kishor Bharti, Dax Koh
Pseudorandom unitaries are neither real nor sparse nor noise-robust Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_71,
title = {Pseudorandom unitaries are neither real nor sparse nor noise-robust},
author = {Tobias Haug and Kishor Bharti and Dax Koh},
url = {https://arxiv.org/abs/2306.11677},
year = {2024},
date = {2024-01-01},
abstract = {Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.
11.
Francesco Anna Mele, Farzin Salek, Vittorio Giovannetti, Ludovico Lami
Quantum communication on the bosonic loss-dephasing channel Talk
2024.
Abstract | Tags: Wednesday | Links:
@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},
url = {https://arxiv.org/abs/2401.15634},
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 not anti-degradable if the loss is below $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 = {Wednesday},
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 not anti-degradable if the loss is below $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.
12.
Jeremiah Blocki, Blake Holman, Seunghoon Lee
Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_243,
title = {Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity},
author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee},
url = {https://eprint.iacr.org/2024/334.pdf https://arxiv.org/pdf/2110.04191},
year = {2024},
date = {2024-01-01},
abstract = {We introduce the parallel reversible pebbling game on directed graphs for constructing parallel quantum circuits that are efficient with respect to amortized space-time complexity (equivalently named cumulative complexity (CC)), a stronger metric than the conventional space-time complexity used for parallel algorithms. Our main result is a mapping from irreversible algorithms for computing a function, to quantum algorithms for computing the function in superposition, with just a sub-polynomial overhead in cumulative complexity. Thus, to construct a CC-efficient quantum oracle for a function, it suffices to solve the simpler problem of designing a CC-efficient classical algorithm for the function. This transformation also allows us to leverage the vast body of work on classical pebbling games for developing parallel quantum circuits with low amortized space-time complexity, given the data-dependency graph of the problem.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
We introduce the parallel reversible pebbling game on directed graphs for constructing parallel quantum circuits that are efficient with respect to amortized space-time complexity (equivalently named cumulative complexity (CC)), a stronger metric than the conventional space-time complexity used for parallel algorithms. Our main result is a mapping from irreversible algorithms for computing a function, to quantum algorithms for computing the function in superposition, with just a sub-polynomial overhead in cumulative complexity. Thus, to construct a CC-efficient quantum oracle for a function, it suffices to solve the simpler problem of designing a CC-efficient classical algorithm for the function. This transformation also allows us to leverage the vast body of work on classical pebbling games for developing parallel quantum circuits with low amortized space-time complexity, given the data-dependency graph of the problem.
13.
Chengkai Zhu, Yin Mo, Yu-Ao Chen, Xin Wang
Reversing Unknown Quantum Processes via Virtual Combs: for Channels with Limited Information Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_110,
title = {Reversing Unknown Quantum Processes via Virtual Combs: for Channels with Limited Information},
author = {Chengkai Zhu and Yin Mo and Yu-Ao Chen and Xin Wang},
url = {https://arxiv.org/abs/2401.04672},
year = {2024},
date = {2024-01-01},
abstract = {The inherent irreversibility of quantum dynamics for open systems poses a significant barrier to the inversion of unknown quantum processes. To tackle this challenge, we propose the framework of virtual combs that exploit the unknown process iteratively with additional classical post-processing to simulate the process inverse. Our research establishes a path to achieving the exact inverse of unknown channels with certain conditions, accompanied by a no-go theorem that underscores the intrinsic limitations imposed by quantum mechanics on such tasks. Notably, we demonstrate that an n-slot virtual comb can exactly reverse a depolarizing channel with one unknown noise parameter out of n+1 potential candidates, and a 1-slot virtual comb can exactly reverse an arbitrary pair of quantum channels. We further explore the approximate inverse of an unknown channel within a given channel set. For any unknown depolarizing channels within a specified noise region, we unveil a worst-case error decay of O(n^−1) of reversing the channel via virtual combs. Moreover, we show that virtual combs with constant slots can be applied to universally reverse unitary operations and investigate the trade-off between the slot number and the sampling overhead.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
The inherent irreversibility of quantum dynamics for open systems poses a significant barrier to the inversion of unknown quantum processes. To tackle this challenge, we propose the framework of virtual combs that exploit the unknown process iteratively with additional classical post-processing to simulate the process inverse. Our research establishes a path to achieving the exact inverse of unknown channels with certain conditions, accompanied by a no-go theorem that underscores the intrinsic limitations imposed by quantum mechanics on such tasks. Notably, we demonstrate that an n-slot virtual comb can exactly reverse a depolarizing channel with one unknown noise parameter out of n+1 potential candidates, and a 1-slot virtual comb can exactly reverse an arbitrary pair of quantum channels. We further explore the approximate inverse of an unknown channel within a given channel set. For any unknown depolarizing channels within a specified noise region, we unveil a worst-case error decay of O(n^−1) of reversing the channel via virtual combs. Moreover, we show that virtual combs with constant slots can be applied to universally reverse unitary operations and investigate the trade-off between the slot number and the sampling overhead.
14.
Robert Salzmann, Bjarne Bergh, Nilanjana Datta
Robustness of Fixed Points of Quantum Channels and Application to Approximate Quantum Markov Chains Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_228,
title = {Robustness of Fixed Points of Quantum Channels and Application to Approximate Quantum Markov Chains},
author = {Robert Salzmann and Bjarne Bergh and Nilanjana Datta},
url = {https://arxiv.org/abs/2405.01532},
year = {2024},
date = {2024-01-01},
abstract = {Given a quantum channel and a state which satisfy a fixed point equation approx-
imately (say, up to an error ε), can one find a new channel and a state, which are
respectively close to the original ones, such that they satisfy an exact fixed point equa-
tion? It is interesting to ask this question for different choices of constraints on the
structures of the original channel and state, and requiring that these are also satisfied
by the new channel and state. We affirmatively answer the above question, under
fairly general assumptions on these structures, through a compactness argument. Ad-
ditionally, for channels and states satisfying certain specific structures, we find explicit
upper bounds on the distances between the pairs of channels (and states) in question.
When these distances decay quickly (in a particular, desirable manner) as ε → 0, we
say that the original approximate fixed point equation is rapidly fixable. We establish
rapid fixability, not only for general quantum channels, but also when the original and
new channels are both required to be unitary, mixed unitary or unital. In contrast,
for the case of bipartite quantum systems with channels acting trivially on one subsys-
tem, we prove that approximate fixed point equations are not rapidly fixable. In this
case, the distance to the closest channel (and state) which satisfy an exact fixed point
equation can depend on the dimension of the quantum system in an undesirable way.
We apply our results on approximate fixed point equations to the question of robust-
ness of quantum Markov chains (QMC) and establish the following: For any tripartite
quantum state, there exists a dimension-dependent upper bound on its distance to the
set of QMCs, which decays to zero as the conditional mutual information of the state vanishes.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Given a quantum channel and a state which satisfy a fixed point equation approx-
imately (say, up to an error ε), can one find a new channel and a state, which are
respectively close to the original ones, such that they satisfy an exact fixed point equa-
tion? It is interesting to ask this question for different choices of constraints on the
structures of the original channel and state, and requiring that these are also satisfied
by the new channel and state. We affirmatively answer the above question, under
fairly general assumptions on these structures, through a compactness argument. Ad-
ditionally, for channels and states satisfying certain specific structures, we find explicit
upper bounds on the distances between the pairs of channels (and states) in question.
When these distances decay quickly (in a particular, desirable manner) as ε → 0, we
say that the original approximate fixed point equation is rapidly fixable. We establish
rapid fixability, not only for general quantum channels, but also when the original and
new channels are both required to be unitary, mixed unitary or unital. In contrast,
for the case of bipartite quantum systems with channels acting trivially on one subsys-
tem, we prove that approximate fixed point equations are not rapidly fixable. In this
case, the distance to the closest channel (and state) which satisfy an exact fixed point
equation can depend on the dimension of the quantum system in an undesirable way.
We apply our results on approximate fixed point equations to the question of robust-
ness of quantum Markov chains (QMC) and establish the following: For any tripartite
quantum state, there exists a dimension-dependent upper bound on its distance to the
set of QMCs, which decays to zero as the conditional mutual information of the state vanishes.
imately (say, up to an error ε), can one find a new channel and a state, which are
respectively close to the original ones, such that they satisfy an exact fixed point equa-
tion? It is interesting to ask this question for different choices of constraints on the
structures of the original channel and state, and requiring that these are also satisfied
by the new channel and state. We affirmatively answer the above question, under
fairly general assumptions on these structures, through a compactness argument. Ad-
ditionally, for channels and states satisfying certain specific structures, we find explicit
upper bounds on the distances between the pairs of channels (and states) in question.
When these distances decay quickly (in a particular, desirable manner) as ε → 0, we
say that the original approximate fixed point equation is rapidly fixable. We establish
rapid fixability, not only for general quantum channels, but also when the original and
new channels are both required to be unitary, mixed unitary or unital. In contrast,
for the case of bipartite quantum systems with channels acting trivially on one subsys-
tem, we prove that approximate fixed point equations are not rapidly fixable. In this
case, the distance to the closest channel (and state) which satisfy an exact fixed point
equation can depend on the dimension of the quantum system in an undesirable way.
We apply our results on approximate fixed point equations to the question of robust-
ness of quantum Markov chains (QMC) and establish the following: For any tripartite
quantum state, there exists a dimension-dependent upper bound on its distance to the
set of QMCs, which decays to zero as the conditional mutual information of the state vanishes.
15.
Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, João Ribeiro
Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World Talk
2024.
Abstract | Tags: Wednesday | Links:
@Talk{T24_263,
title = {Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World},
author = {Alper Çakan and Vipul Goyal and Chen-Da Liu-Zhang and João Ribeiro},
url = {https://eprint.iacr.org/2023/410},
year = {2024},
date = {2024-01-01},
abstract = {Can an adversary compromise the security of our system by obtaining information on sensitive data such as cryptographic keys through side-channels? Even worse, can an adversary hack into our computer and simply steal them? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect such attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world? We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the leakage-resilient cryptography literature. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against. As a notable example, the most well-studied leakage model is that of bounded leakage, where it is assumed that an adversary learns at most L bits of leakage on secret components, for some leakage bound L. Although this leakage bound is necessary, many real-world side-channel attacks cannot be captured by bounded leakage. In this work, we design cryptographic schemes that provide guarantees against arbitrary side channel attacks:
- Using techniques from unclonable quantum cryptography, we design several basic leakage- resilient primitives, such as public- and private-key encryption, (weak) pseudorandom functions, digital signatures and quantum money schemes which remain secure under (polynomially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classical information. Notably, the leakage-resilience of our schemes holds even in the stronger “LOCC leakage” model where the adversary can obtain adaptive leakage for unbounded number of rounds. - What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack?What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? We initiate the study of intrusion detection in the quantum setting, where one would like to detect if security has been compromised even in the face of an arbitrary intruder attack which can leak and tamper with classical as well as quantum data. We design cryptographic schemes supporting intrusion-detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion.},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Talk}
}
Can an adversary compromise the security of our system by obtaining information on sensitive data such as cryptographic keys through side-channels? Even worse, can an adversary hack into our computer and simply steal them? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect such attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world? We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the leakage-resilient cryptography literature. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against. As a notable example, the most well-studied leakage model is that of bounded leakage, where it is assumed that an adversary learns at most L bits of leakage on secret components, for some leakage bound L. Although this leakage bound is necessary, many real-world side-channel attacks cannot be captured by bounded leakage. In this work, we design cryptographic schemes that provide guarantees against arbitrary side channel attacks:
- Using techniques from unclonable quantum cryptography, we design several basic leakage- resilient primitives, such as public- and private-key encryption, (weak) pseudorandom functions, digital signatures and quantum money schemes which remain secure under (polynomially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classical information. Notably, the leakage-resilience of our schemes holds even in the stronger “LOCC leakage” model where the adversary can obtain adaptive leakage for unbounded number of rounds. - What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack?What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? We initiate the study of intrusion detection in the quantum setting, where one would like to detect if security has been compromised even in the face of an arbitrary intruder attack which can leak and tamper with classical as well as quantum data. We design cryptographic schemes supporting intrusion-detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion.
- Using techniques from unclonable quantum cryptography, we design several basic leakage- resilient primitives, such as public- and private-key encryption, (weak) pseudorandom functions, digital signatures and quantum money schemes which remain secure under (polynomially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classical information. Notably, the leakage-resilience of our schemes holds even in the stronger “LOCC leakage” model where the adversary can obtain adaptive leakage for unbounded number of rounds. - What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack?What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? We initiate the study of intrusion detection in the quantum setting, where one would like to detect if security has been compromised even in the face of an arbitrary intruder attack which can leak and tamper with classical as well as quantum data. We design cryptographic schemes supporting intrusion-detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion.
