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
@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_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_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_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}
}
@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_275,
title = {Advantage of Quantum Machine Learning from General Computational Advantages},
author = {Hayata Yamasaki and Natsuto Isogai and Mio Murao},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_138,
title = {Advantage of Quantum Neural Networks as Quantum Information Decoders},
author = {Oles Shtanko and Weishun Zhong and Ramis Movassagh},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_165,
title = {Alchemy of quantum coherence: Arbitrary amplification in catalytic and asymptotic coherence manipulation},
author = {Naoto Shiraishi and Ryuji Takagi},
url = {https://arxiv.org/abs/2308.12338},
year = {2024},
date = {2024-01-01},
abstract = {Quantum coherence is one of the fundamental aspects distinguishing classical and quantum theories. Coherence between different energy eigenstates is particularly important, as it serves as a valuable resource under the law of energy conservation. A fundamental question in this setting is how well one can prepare good coherent states from low coherent states and whether a given coherent state is convertible to another one. Here, we show that any low coherent state is convertible to any high coherent state arbitrarily well in two operational settings: asymptotic and catalytic transformations. For a variant of asymptotic coherence manipulation where one aims to prepare desired states in local subsystems, the rate of transformation becomes unbounded regardless of how weak the initial coherence is. In a non-asymptotic transformation with a catalyst, a helper state that locally remains in the original form after the transformation, we show that an arbitrary state can be obtained from any low coherent state. Applying this to the standard asymptotic setting, we find that a catalyst can increase the coherence distillation rate significantly—from zero to infinite rate. We also prove that such anomalous transformation requires small but non-zero coherence in relevant modes, establishing the condition under which a sharp transition of the operational capability occurs. Our results provide a general characterization of the coherence transformability in these operational settings and showcase their peculiar properties compared to other common resource theories such as entanglement and quantum thermodynamics.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
Quantum coherence is one of the fundamental aspects distinguishing classical and quantum theories. Coherence between different energy eigenstates is particularly important, as it serves as a valuable resource under the law of energy conservation. A fundamental question in this setting is how well one can prepare good coherent states from low coherent states and whether a given coherent state is convertible to another one. Here, we show that any low coherent state is convertible to any high coherent state arbitrarily well in two operational settings: asymptotic and catalytic transformations. For a variant of asymptotic coherence manipulation where one aims to prepare desired states in local subsystems, the rate of transformation becomes unbounded regardless of how weak the initial coherence is. In a non-asymptotic transformation with a catalyst, a helper state that locally remains in the original form after the transformation, we show that an arbitrary state can be obtained from any low coherent state. Applying this to the standard asymptotic setting, we find that a catalyst can increase the coherence distillation rate significantly—from zero to infinite rate. We also prove that such anomalous transformation requires small but non-zero coherence in relevant modes, establishing the condition under which a sharp transition of the operational capability occurs. Our results provide a general characterization of the coherence transformability in these operational settings and showcase their peculiar properties compared to other common resource theories such as entanglement and quantum thermodynamics.
@Poster{P24_171,
title = {Algebra of Nonlocal Boxes and the Collapse of Communication Complexity},
author = {Pierre Botteron and Anne Broadbent and Reda Chhaibi and Ion Nechita and Clément Pellegrini},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_52,
title = {Algorithmic Cluster Expansions for Quantum Problems},
author = {Ryan Mann and Romy Minko},
url = {https://arxiv.org/abs/2306.08974 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1716175598-poster-52.pdf},
year = {2024},
date = {2024-01-01},
abstract = {We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of abstract polymer models formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of abstract polymer models formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.
@Poster{P24_170,
title = {All graph state verification protocols are composably secure},
author = {Léo Colisson and Damian Markham and Raja Yehia},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_289,
title = {Alleviating the quantum Big-M problem},
author = {Edoardo Alessandroni and Sergi Ramos-Calderer and Ingo Roth},
url = {https://arxiv.org/abs/2307.10379},
year = {2024},
date = {2024-01-01},
abstract = {A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the "Big-M" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the "Big-M" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.
@Poster{P24_210,
title = {Approximation Algorithms for Quantum Max-d-Cut},
author = {Zackary Jorquera and Steven Kordonowy and Stuart Wayland and Alexandra Kolla and Charlie Carlson},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_179,
title = {Assessing non-Markovian dynamics through moments of the Choi state},
author = {Bivas Mallick and Saheli Mukherjee and Ananda Gopal Maity and Archan S. Majumdar},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_231,
title = {Bases for optimising stabiliser decompositions of quantum states},
author = {Nadish Silva and Ming Yin and Sergii Strelchuk},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_90,
title = {Bayesian inference of quantum devices},
author = {Michele Dall'Arno},
url = {https://arxiv.org/abs/2304.13258},
year = {2024},
date = {2024-01-01},
abstract = {We consider the scenario in which a black box with buttons and light bulbs is given so that, if any button is pressed a certain number of times, the corresponding probability distribution on the light bulbs lighting up can be observed. We model the black box as a prepare-and-measure setup, that is, an unspecified state is prepared upon the pressure of any button, and an unspecified measurement is performed on such a state.
We consider the problem of the Bayesian inference of, say, the measurement (but, of course, we could consider the dual problem of inferring the states), that is, we aim at finding the measurement that maximizes the Bayesian posterior probability density, given the observations, for any given prior probability density on states and measurements.
Our main result is to characterize such optimal measurements in the informationally complete (IC) case when uniform probability densities (i.e. maximal ignorance) are assumed on states and measurements. In particular, we prove that any measurement that produces the observations upon the input of a 2-design set of states is optimal, thus settling in closed-form the case of non-overcomplete measurements, for which the only 2-design is the symmetric, informationally complete (SIC) set of states. Being data-driven, the inferential setup we consider offers a solution to the chicken-or-egg problem of usual quantum tomography, that is, the fact that the tomography of a measurement requires the knowledge of the input states, whereas the tomography of the states requires the knowledge of the measurement, in a neverending loop.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
We consider the scenario in which a black box with buttons and light bulbs is given so that, if any button is pressed a certain number of times, the corresponding probability distribution on the light bulbs lighting up can be observed. We model the black box as a prepare-and-measure setup, that is, an unspecified state is prepared upon the pressure of any button, and an unspecified measurement is performed on such a state.
We consider the problem of the Bayesian inference of, say, the measurement (but, of course, we could consider the dual problem of inferring the states), that is, we aim at finding the measurement that maximizes the Bayesian posterior probability density, given the observations, for any given prior probability density on states and measurements.
Our main result is to characterize such optimal measurements in the informationally complete (IC) case when uniform probability densities (i.e. maximal ignorance) are assumed on states and measurements. In particular, we prove that any measurement that produces the observations upon the input of a 2-design set of states is optimal, thus settling in closed-form the case of non-overcomplete measurements, for which the only 2-design is the symmetric, informationally complete (SIC) set of states. Being data-driven, the inferential setup we consider offers a solution to the chicken-or-egg problem of usual quantum tomography, that is, the fact that the tomography of a measurement requires the knowledge of the input states, whereas the tomography of the states requires the knowledge of the measurement, in a neverending loop.
@Poster{P24_35,
title = {BQP, meet NP: Search-to-decision reductions and approximate counting},
author = {Jonas Kamminga and Sevag Gharibian},
url = {https://arxiv.org/abs/2401.03943},
year = {2024},
date = {2024-01-01},
abstract = {What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPP^NP[o(n)] contains a P^NP-complete problem if the algorithm is classical and FBQP^NP[o(n)] contains an FP^NP-complete problem if the algorithm is quantum.},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPP^NP[o(n)] contains a P^NP-complete problem if the algorithm is classical and FBQP^NP[o(n)] contains an FP^NP-complete problem if the algorithm is quantum.
@Poster{P24_37,
title = {Can we stochastically distil quantum steering and measurement incompatibility?},
author = {Chung-Yun Hsieh and Huan-Yu Ku and Shin-Liang Chen and Yueh-Nan Chen and Costantino Budroni},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_164,
title = {Causal Classification of Spatiotemporal Quantum Correlations},
author = {Minjeong Song and Varun Narasimhachar and Bartosz Regula and Thomas Elliott and Mile Gu},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_88,
title = {Causal influence versus signalling for interacting quantum channels},
author = {Kathleen Barsse and Paolo Perinotti and Alessandro Tosini and Leonardo Vaglini},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_95,
title = {Certifying entanglement dimensionality by the moment method},
author = {Changhao Yi and Xiaodi Li and Huangjun Zhu},
year = {2024},
date = {2024-01-01},
abstract = {In this paper, we combine the k-reduction map, the moment method and the classical shadow
method into a practical entanglement dimensionality certification protocol. The core of our protocol
utilizes finite order reduction moments of the target state to determine if it remains positive under
the application of the k-reduction map. First, we study the spectrum of the k-reduced operators.
Further, similar with the entanglement negativity, we introduce the definition of k-reduction neg-
ativity, explore its properties to characterize the violation of the criterion. Second, we apply the
moment methods to the k-reduction map, and construct the reduction moment criteria systemati-
cally by considering the spectrum information. Our final protocol applies to a much wider range of
states than the fidelity-based methods. Additionally, our method only requires a unitary-3 design,
making it more feasible in practice than the correlation matrix method. We further explore the de-
tectable abilities of different protocols and demonstrate the efficiency of our protocol with analytical and numerical examples},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
In this paper, we combine the k-reduction map, the moment method and the classical shadow
method into a practical entanglement dimensionality certification protocol. The core of our protocol
utilizes finite order reduction moments of the target state to determine if it remains positive under
the application of the k-reduction map. First, we study the spectrum of the k-reduced operators.
Further, similar with the entanglement negativity, we introduce the definition of k-reduction neg-
ativity, explore its properties to characterize the violation of the criterion. Second, we apply the
moment methods to the k-reduction map, and construct the reduction moment criteria systemati-
cally by considering the spectrum information. Our final protocol applies to a much wider range of
states than the fidelity-based methods. Additionally, our method only requires a unitary-3 design,
making it more feasible in practice than the correlation matrix method. We further explore the de-
tectable abilities of different protocols and demonstrate the efficiency of our protocol with analytical and numerical examples
@Poster{P24_97,
title = {Certifying long-range quantum correlations in routed Bell tests},
author = {Edwin Peter Lobo and Jef Pauwels and Stefano Pironio},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_144,
title = {Classical algorithm for simulating experimental Gaussian boson sampling},
author = {Changhun Oh and Minzhao Liu and Yuri Alexeev and Bill Fefferman and Liang Jiang},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
@Poster{P24_153,
title = {Clifford Group and Unitary Designs under Symmetry},
author = {Yosuke Mitsuhashi and Nobuyuki Yoshioka},
year = {2024},
date = {2024-01-01},
keywords = {Poster session Monday},
pubstate = {published},
tppubtype = {Poster}
}
