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_208,
title = {A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits},
author = {Libor Caha and Xavier Coiteux-Roy and Robert Koenig},
url = {https://arxiv.org/abs/2312.09209},
year = {2024},
date = {2024-01-01},
abstract = {We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Talk}
}
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.
@Poster{P24_382,
title = {A Complete Graphical Language for Linear Optical Circuits with Finite-Photon-Number Sources and Detectors},
author = {Nicolas Heurtel},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Talk{T24_235,
title = {A Computational Tsirelson's Theorem for the Value of Compiled XOR Games},
author = {David Cui and Giulio Malavolta and Arthur Mehta and Anand Natarajan and Connor Paddock and Simon Schmidt and Michael Walter and Tina Zhang},
url = {https://arxiv.org/abs/2402.17301},
year = {2024},
date = {2024-01-01},
abstract = {Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Talk}
}
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.
@Poster{P24_398,
title = {A Cryptographic Perspective on the Verifiability of Quantum Advantage},
author = {Nai-Hui Chia and Honghao Fu and Fang Song and Penghui Yao},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Talk{T24_288,
title = {A Direct Reduction from the Polynomial to the Adversary Method},
author = {Aleksandrs Belovs},
year = {2024},
date = {2024-01-01},
abstract = {The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.},
keywords = {Monday, Proceedings},
pubstate = {published},
tppubtype = {Talk}
}
The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.
@Poster{P24_297,
title = {A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems},
author = {Samuel Scalet},
url = {https://arxiv.org/abs/2402.19030},
year = {2024},
date = {2024-01-01},
abstract = {We consider the problem of approximating the free energy density of a translation-invariant, one-dimensional quantum spin system with finite range. While the complexity of this problem is nontrivial due to its close connection to problems with known hardness results, a classical subpolynomial-time algorithm has recently been proposed [Fawzi et al., 2022]. Combining several algorithmic techniques previously used for related problems, we propose an algorithm outperforming this result asymptotically and give rigorous bounds on its runtime. Our main techniques are the use of Araki expansionals, known from results on the nonexistence of phase transitions, and a matrix product operator construction. We also review a related approach using the Quantum Belief Propagation [Kuwahara et al., 2018], which in combination with our findings yields an equivalent result.},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
We consider the problem of approximating the free energy density of a translation-invariant, one-dimensional quantum spin system with finite range. While the complexity of this problem is nontrivial due to its close connection to problems with known hardness results, a classical subpolynomial-time algorithm has recently been proposed [Fawzi et al., 2022]. Combining several algorithmic techniques previously used for related problems, we propose an algorithm outperforming this result asymptotically and give rigorous bounds on its runtime. Our main techniques are the use of Araki expansionals, known from results on the nonexistence of phase transitions, and a matrix product operator construction. We also review a related approach using the Quantum Belief Propagation [Kuwahara et al., 2018], which in combination with our findings yields an equivalent result.
@Poster{P24_416,
title = {A framework of partial error correction for intermediate-scale quantum computers},
author = {Nikolaos Koukoulekidis and Samson Wang and Tom O'Leary and Daniel Bultrini and Lukasz Cincio and Piotr Czarnik},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_506,
title = {A general purification protocol with imperfect state preparation},
author = {Golshan Lirabi and Faedi Loulidi and David Elkouss},
year = {2024},
date = {2024-01-01},
abstract = {Purification protocols take several copies of a
mixed state and output a smaller number of copies with
higher purity. Recently, a protocol based on the Swap test
was shown to have optimal resource consumption, with
the number of samples scaling proportional to the inverse
of the error. In this work, we consider a more realistic
scenario in which all the prepared states are noisy,
including the auxiliary qubits used by the protocol. Here,
we show that this generalization does not compromise
convergence, with the protocol still converging for all non
extreme noise values. Moreover, we estimate the number
of iterations and resources needed in the generalized
scenario. Such an estimation allows us to address the
optimality of the protocol with noisy state preparation and show that the protocol is no longer optimal.},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
Purification protocols take several copies of a
mixed state and output a smaller number of copies with
higher purity. Recently, a protocol based on the Swap test
was shown to have optimal resource consumption, with
the number of samples scaling proportional to the inverse
of the error. In this work, we consider a more realistic
scenario in which all the prepared states are noisy,
including the auxiliary qubits used by the protocol. Here,
we show that this generalization does not compromise
convergence, with the protocol still converging for all non
extreme noise values. Moreover, we estimate the number
of iterations and resources needed in the generalized
scenario. Such an estimation allows us to address the
optimality of the protocol with noisy state preparation and show that the protocol is no longer optimal.
@Poster{P24_260,
title = {A little magic means a lot},
author = {Andi Gu and Lorenzo Leone and Soumik Ghosh and Jens Eisert and Susanne Yelin and Yihui Quek},
url = {https://arxiv.org/abs/2308.16228},
year = {2024},
date = {2024-01-01},
abstract = {Notions of nonstabilizerness, or ``magic'', quantify how non-classical quantum states are in a precise sense: states exhibiting low nonstabilizerness preclude quantum advantage. We introduce `pseudomagic' ensembles of quantum states that, despite low nonstabilizerness, are computationally indistinguishable from those with high nonstabilizerness. Previously, such computational indistinguishability has been studied with respect to entanglement, introducing the concept of pseudoentanglement. However, we demonstrate that pseudomagic neither follows from pseudoentanglement nor implies it. In terms of applications, the study of pseudomagic offers fresh insights into the theory of quantum scrambling: it uncovers states that, even though they originate from non-scrambling unitaries, remain indistinguishable from scrambled states to any physical observer. Additional applications include new lower bounds on state synthesis problems, property testing protocols, and implications for quantum cryptography. Our work is driven by the observation that only quantities measurable by a computationally bounded observer – intrinsically limited by finite-time computational constraints – hold physical significance. Ultimately, our findings suggest that nonstabilizerness is a `hide-able' characteristic of quantum states: some states are much more magical than is apparent to a computationally bounded observer.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
Notions of nonstabilizerness, or ``magic'', quantify how non-classical quantum states are in a precise sense: states exhibiting low nonstabilizerness preclude quantum advantage. We introduce `pseudomagic' ensembles of quantum states that, despite low nonstabilizerness, are computationally indistinguishable from those with high nonstabilizerness. Previously, such computational indistinguishability has been studied with respect to entanglement, introducing the concept of pseudoentanglement. However, we demonstrate that pseudomagic neither follows from pseudoentanglement nor implies it. In terms of applications, the study of pseudomagic offers fresh insights into the theory of quantum scrambling: it uncovers states that, even though they originate from non-scrambling unitaries, remain indistinguishable from scrambled states to any physical observer. Additional applications include new lower bounds on state synthesis problems, property testing protocols, and implications for quantum cryptography. Our work is driven by the observation that only quantities measurable by a computationally bounded observer – intrinsically limited by finite-time computational constraints – hold physical significance. Ultimately, our findings suggest that nonstabilizerness is a `hide-able' characteristic of quantum states: some states are much more magical than is apparent to a computationally bounded observer.
@Poster{P24_322,
title = {A Max-Flow approach to Random Tensor Networks},
author = {Faedi Loulidi and Khurshed Fitter and Ion Nechita},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_291,
title = {A Note on Exponential Quantum One-Wayness},
author = {Giulio Malavolta and Tomoyuki Morimae and Michael Walter and Takashi Yamakawa},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_44,
title = {A Note on Output Length of One-Way State Generators and EFIs},
author = {Minki Hhan and Tomoyuki Morimae and Takashi Yamakawa},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_524,
title = {A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions},
author = {Eleni Diamanti and Alex Bredariol Grilo and Adriano Innocenzi and Pascal Lefebvre and Verena Yacoub and Alvaro Yángüez},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_512,
title = {A pure (2+1)-dimensional SU(2) model for analog simulation in small-scale superconducting quantum devices},
author = {Lucia Valor and Klaus Liegener and Stefan Filipp and Peter Rabl},
year = {2024},
date = {2024-01-01},
abstract = {Lattice gauge theories constitute an important tool in studying the fundamental interactions of matter within particle physics and have a wide range of applications in condensed matter physics and quantum information theory. While classical numerical methods can be used to simulate many properties of Abelian and non-Abelian gauge theories efficiently, the intrinsic quantum nature of these theories makes other relevant physical phenomena hard to reproduce. Quantum simulators offer a promising approach to address these challenges, with successful simulations of Abelian theories in different quantum platforms demonstrating their potential in the last decades. Despite these advances, quantum simulation of non-Abelian theories remains challenging. Recent research efforts aimed at the analog simulation of these gauge theories have predominantly focused on atomic quantum platforms like ultracold atoms and trapped ions. Here, we propose a minimal model for a (2+1)-dimensional pure SU(2) lattice gauge theory, implementable as an analog simulation on superconducting quantum hardware. We study properties of the system, such as the effect of adding bosonic excitations, and explore its experimental implementation. Our work contributes to the exploration and understanding of non-Abelian gauge theories and offers a new and rich implementation to study lattice gauge theories using superconducting qubits.},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
Lattice gauge theories constitute an important tool in studying the fundamental interactions of matter within particle physics and have a wide range of applications in condensed matter physics and quantum information theory. While classical numerical methods can be used to simulate many properties of Abelian and non-Abelian gauge theories efficiently, the intrinsic quantum nature of these theories makes other relevant physical phenomena hard to reproduce. Quantum simulators offer a promising approach to address these challenges, with successful simulations of Abelian theories in different quantum platforms demonstrating their potential in the last decades. Despite these advances, quantum simulation of non-Abelian theories remains challenging. Recent research efforts aimed at the analog simulation of these gauge theories have predominantly focused on atomic quantum platforms like ultracold atoms and trapped ions. Here, we propose a minimal model for a (2+1)-dimensional pure SU(2) lattice gauge theory, implementable as an analog simulation on superconducting quantum hardware. We study properties of the system, such as the effect of adding bosonic excitations, and explore its experimental implementation. Our work contributes to the exploration and understanding of non-Abelian gauge theories and offers a new and rich implementation to study lattice gauge theories using superconducting qubits.
@Poster{P24_412,
title = {A quantum algorithm for the pathfinding problem via the quantum electrical flow},
author = {Jianqiang Li and Sean Hallgren},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_5,
title = {A Quantum Approximation Scheme for k-Means},
author = {Ragesh Jaiswal},
url = {https://arxiv.org/abs/2308.08167},
year = {2024},
date = {2024-01-01},
abstract = {We give a quantum approximation scheme (i.e., (1+ε)-approximation for every ε>0) for the classical k-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of (1+ε) for the k-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
We give a quantum approximation scheme (i.e., (1+ε)-approximation for every ε>0) for the classical k-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of (1+ε) for the k-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.
@Poster{P24_334,
title = {A quasi-polynomial time classical algorithm for almost any noisy quantum circuit},
author = {Thomas Schuster and Norman Y. Yao},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_212,
title = {A security framework for quantum key distribution implementations},
author = {Guillermo Currás-Lorenzo and Margarida Pereira and Go Kato and Marcos Curty and Kiyoshi Tamaki},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Talk{T24_325,
title = {A shortcut to a near-optimal quantum linear system solver},
author = {Alexander Dalzell},
year = {2024},
date = {2024-01-01},
abstract = {Given a linear system of equations Ax = b, quantum linear system solvers (QLSSs) approximately prepare a quantum state |x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant factors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple, near-optimal QLSS that does not use these techniques. If the solution norm ∥x∥∥A∥/∥b∥ is known exactly, our QLSS requires only a single application of kernel reflection (an extension of eigenstate filtering), and has query complexity (1 + O(ε))κ ln(2√2/ε). If the norm is not known, it can be estimated up to a constant factor using O(log log(κ)) applications of kernel projection (a slight generalization of eigenstate filtering), yielding a QLSS with near-optimal total complexity O(κ log log(κ) log log log(κ) + κ log(1/ε)). Preliminary constant-factor analysis suggests that for practical values of κ, ε our QLSS provides rigorous guarantees that are at least an order of magnitude better than previous guarantees.},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Talk}
}
Given a linear system of equations Ax = b, quantum linear system solvers (QLSSs) approximately prepare a quantum state |x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant factors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple, near-optimal QLSS that does not use these techniques. If the solution norm ∥x∥∥A∥/∥b∥ is known exactly, our QLSS requires only a single application of kernel reflection (an extension of eigenstate filtering), and has query complexity (1 + O(ε))κ ln(2√2/ε). If the norm is not known, it can be estimated up to a constant factor using O(log log(κ)) applications of kernel projection (a slight generalization of eigenstate filtering), yielding a QLSS with near-optimal total complexity O(κ log log(κ) log log log(κ) + κ log(1/ε)). Preliminary constant-factor analysis suggests that for practical values of κ, ε our QLSS provides rigorous guarantees that are at least an order of magnitude better than previous guarantees.
@Poster{P24_476,
title = {A Unified Theory of Barren Plateaus for Deep Parametrized Quantum Circuits},
author = {Martin Larocca and Marco Cerezo and Frederic Sauvage and Michael Ragone and Bojko Bakalov and Alexander Kemper and Carlos Ortiz Marrero},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_328,
title = {Accelerated Convergence in Training Quantum Neural Network with Modest Depths},
author = {Kaining Zhang and Junyu Liu and Liu Liu and Liang Jiang and Min-Hsiu Hsieh and Dacheng Tao},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_9,
title = {Accelerating quantum optimal control of multi-qubit systems with symmetry-based Hamiltonian transformations},
author = {Xian Wang and Mahmut Sait Okyay and Bryan M. Wong},
url = {https://doi.org/10.1116/5.0162455},
year = {2024},
date = {2024-01-01},
abstract = {We present a novel, computationally efficient approach to accelerate quantum optimal control calculations of large multi-qubit systems. By leveraging the system's intrinsic symmetry, the Hilbert space can be decomposed and the Hamiltonians block diagonalized to enable extremely fast quantum optimal control calculations. Our approach reduces the computational runtime of qubit optimal control calculations by orders of magnitude while maintaining the same accuracy as the original method. This symmetry-based method can be generalized to a variety of multi-qubit systems with Trotterization techniques. As prospective applications, we propose the concept of symmetry-protected subspaces, which can be potential platforms for preparing symmetric states, realizing quantum gates simultaneously, quantum error suppression, and quantum simulation.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
We present a novel, computationally efficient approach to accelerate quantum optimal control calculations of large multi-qubit systems. By leveraging the system's intrinsic symmetry, the Hilbert space can be decomposed and the Hamiltonians block diagonalized to enable extremely fast quantum optimal control calculations. Our approach reduces the computational runtime of qubit optimal control calculations by orders of magnitude while maintaining the same accuracy as the original method. This symmetry-based method can be generalized to a variety of multi-qubit systems with Trotterization techniques. As prospective applications, we propose the concept of symmetry-protected subspaces, which can be potential platforms for preparing symmetric states, realizing quantum gates simultaneously, quantum error suppression, and quantum simulation.
@Poster{P24_80,
title = {Achieving the Heisenberg limit with Dicke States in noisy quantum meterology},
author = {Zain Saleem and Michael A Perlin and Anil Shaji and Stephen Gray},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_469,
title = {Activation of post-quantumness in generalized EPR scenarios},
author = {Beata Zjawin and Matty Hoban and Ana Belén Sainz and Paul Skrzypczyk},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_503,
title = {Advances in quantum algorithms for the shortest s-t path problem.},
author = {Adam Wesolowski and Stephen Piddock},
year = {2024},
date = {2024-01-01},
abstract = {We study a fundamental problem in graph theory of finding the shortest path between vertices in
an undirected, weighted graph. We present quantum algorithms in the adjacency array model which for the considered instances show a polynomial separation over the best known classical and quantum algorithms. First of our approaches is based on sampling the quantum flow state in a divide and conquer framework. Our second approach is based on querying the classical shadow of the quantum flow state and following a greedy algorithm. In particular, we show that using O(m) space we can find the shortest path in time that is asymptotically equal to the time required for detecting a path.},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
We study a fundamental problem in graph theory of finding the shortest path between vertices in
an undirected, weighted graph. We present quantum algorithms in the adjacency array model which for the considered instances show a polynomial separation over the best known classical and quantum algorithms. First of our approaches is based on sampling the quantum flow state in a divide and conquer framework. Our second approach is based on querying the classical shadow of the quantum flow state and following a greedy algorithm. In particular, we show that using O(m) space we can find the shortest path in time that is asymptotically equal to the time required for detecting a path.
@Poster{P24_559,
title = {Advantage of Hardy's nonlocal correlation in reverse zero-error channel coding},
author = {Mir Alimuddin and Ananya Chakraborty and Govind Lal Sidhardh and Ram Krishna Patra and Samrat Sen and Sahil Gopalkrishna Naik and Manik Banik},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Thursday},
pubstate = {published},
tppubtype = {Poster}
}
