The Theory of Quantum Computation, Communication and Cryptography (TQC) is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.
The 19th TQC was hosted by OIST in Okinawa, Japan, in September 2024. It was a hybrid event, with focus on in-person participation. Talks were streamed live.
Potential and Limitations of Near-Term Quantum Computing
Quantum computers promise the efficient solution of some highly structured computational problems that are classically intractable. While for many years they have been primarily objects of theoretical study, only recently have efforts to build intermediate-scale quantum computers taken off. This creates an interesting state of affairs, but at the same time, it begs the question of what such devices are, practically speaking, good for. In this talk, we will present some encouraging as well as—emphasizing the latter—discouraging insights into near-term quantum computing. We will discuss rigorous quantum advantages in paradigmatic problems [1,2] and explore the use of quantum computers in machine learning [3,4] and optimization [5]. The second part of the talk will focus on the significant limitations that arise. We will emphasize identifying limitations to quantum error mitigation for shallow quantum circuits in the worst case [6]. Interestingly, it may depend on the nuances of non-unital quantum noise to what extent quantum computing without error correction may be feasible [7]. We will also provide efficient classical algorithms for instances of quantum algorithms, hence "de-quantizing" them [7-9]. The talk will conclude with the note that quantum simulation remains, to date, one of the most promising applications of near-term quantum devices [10,11].
Forward and Backward Mappings for Quantum Graphical Models
Graphical models offer a unifying framework for various statistical learning algorithms and models. Central to these models are the forward and backward mapping problems, which have been studied through both exact and approximate algorithms. This talk explores these mapping problems within the context of quantum graphical models, where quantum states generalize classical probability distributions. The forward mapping problem involves deriving mean parameters from model parameters and is closely linked to approximating the partition function---a typically challenging task often requiring heuristics and approximations. We'll discuss quantum belief propagation, which has shown success in one-dimensional systems, as well as variational methods such as Markov entropy decomposition that tackle the problem from an optimization perspective. The task of the backward mapping problem aims to compute model parameters from mean parameters. It is related to the Hamiltonian learning problem, a topic of growing interest in quantum information science lately. We'll review some existing algorithms and introduce the quantum iterative scaling (QIS) algorithm that reduces the backward mapping problem to a series of forward mapping problems. We'll present a convergence proof for QIS and demonstrate its advantages over gradient descent methods. Furthermore, we'll explore how quasi-Newton methods can enhance QIS and gradient descent algorithms, showcasing significant efficiency improvements.
DakshitaKhurana
University of Illinois Urbana-Champaign
Understanding Cryptographic Hardness in a Quantum World
A flurry of exciting, recent work has shown that the mathematical hardness required to realize cryptosystems such as bit commitments and secure computation in a quantum world can be significantly weaker than the hardness required for classical cryptography. This talk will discuss recent progress and some remaining challenges in understanding the assumptions that enable cryptography in a quantum world.
Tomoyuki Morimae
Yukawa Institute for Theoretical Physics, Kyoto University
Quantum cryptography without one-way functions
The existence of one-way functions is the minimum assumption in classical cryptography. On the other hand, in quantum cryptography where quantum computing and quantum communications are possible, recent studies have demonstrated that the existence of one-way functions is not necessarily the minimum assumption. Several new fundamental primitives have been introduced, such as pseudorandom unitaries, pseudorandom states, one-way state generators, EFI pairs, and one-way puzzles. They seem to be weaker than one-way functions, but still imply many useful applications, such as secret-key encryption, message authentication codes, digital signatures, private-key quantum money, commitments, and multiparty computations, etc. In this talk, I explain the basics of this “quantum cryptography without one-way functions” and give many open problems that I want to know the answers to.
Sponsors and organization of TQC 2023
Platinum sponsors
JPMorganChase
The Quantum Computing team at JPMorganChase's Global Technology Applied Research Center is at the forefront of advancing both the theoretical and practical aspects of quantum and quantum-inspired algorithms. They are currently seeking talented individuals for summer internships, as well as full-time positions for research scientists and software engineers at all experience levels. Join the firm in pushing the boundaries of quantum computing technology. Apply for open positions here.
Gold sponsors
Google Quantum AI
Gold Sponsor
Google Quantum AI is advancing the state of the art of quantum computing and developing the tools for researchers to operate beyond classical capabilities. Our mission is to make best-in-class quantum computing tools available to the world, enabling humankind to solve problems that would otherwise be impossible.
Horizon Quantum Computing is developing a new generation of programming tools to simplify and expedite the process of developing software for quantum computers. By removing the need for prior quantum computing experience to develop applications for quantum hardware, Horizon’s tools are making the power of quantum computing accessible to every software developer.
Quantinuum's mission is to accelerate quantum computing and use its power to positively transform the world. By applying the laws of quantum physics to computing, we will achieve unprecedented breakthroughs in drug discovery, healthcare, materials science, cybersecurity, energy transformation, and climate change.
Japan National Tourism Organization
Silver Sponsor
JNTO is involved in a broad range of activities both domestically and worldwide, to encourage international tourists from all over the world to visit Japan.
People and Committees of TQC 2024
Steering Committee of TQC 2024
Andris Ambainis, University of Latvia
Eric Chitambar, University of Illinois at Urbana-Champaign
@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.
@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.
@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
@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.
@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.
@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.
@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.
@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.
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
@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.
@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.
@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.
@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.
@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.
@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.
@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.
