The poster session will be on Tuesday afternoon (see schedule). The posters will stay up all week in the Department of Mathematics.
The online poster presentations will take place through dedicated Audio/Video channels on the TQC Discord server. You can present your poster during the poster session or at any other time during the conference; all instructions can be found on the Discord server.
Note that not all accepted posters will be presented at the conference due to author availability constraints. If you cannot present your poster, you don’t need to email us.
301.
Zixuan Liu, Ming Yang, Giulio Chiribella
Quantum communication through devices in an indefinite input-output direction Poster
2023.
@Poster{P6863,
title = {Quantum communication through devices in an indefinite input-output direction},
author = {Zixuan Liu and Ming Yang and Giulio Chiribella},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
302.
Jinge Bao
Quantum complexity of computing and estimating diameter in unweighted graph Poster
2023.
@Poster{P1246,
title = {Quantum complexity of computing and estimating diameter in unweighted graph},
author = {Jinge Bao},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
303.
Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtech Havlicek, Guanyu Zhu
Quantum complexity of the Kronecker coefficients Poster
2023.
@Poster{P5435,
title = {Quantum complexity of the Kronecker coefficients},
author = {Sergey Bravyi and Anirban Chowdhury and David Gosset and Vojtech Havlicek and Guanyu Zhu},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
304.
Ryotaro Suzuki, Jonas Haferkamp, Jens Eisert, Philippe Faist
Quantum complexity phase transition in monitored random circuits Poster
2023.
@Poster{P5937,
title = {Quantum complexity phase transition in monitored random circuits},
author = {Ryotaro Suzuki and Jonas Haferkamp and Jens Eisert and Philippe Faist},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
305.
Marco Aldi, Sevag Gharibian, Dorian Rudolph
Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits Talk
2024.
@Talk{T24_50,
title = {Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits},
author = {Marco Aldi and Sevag Gharibian and Dorian Rudolph},
year = {2024},
date = {2024-01-01},
abstract = {The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite being a classical complexity class, however, TFNP has made a surprise appearance in the study of Quantum Satisfiability (QSAT): If a QSAT instance has a System of Distinct Representatives (SDR), then it has a product-state solution [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Efficiently finding this product-state solution, however, has remained elusive. In this work, we introduce a new framework based on Weighted SDRs (WSDR), which among other results, allows us to: (1) significantly simplify and extend the results of [LLMSS 2010] to qudit systems, (2) establish a connection to the Bézout number for multihomogeneous polynomial systems, and (3) apply the parameterized algorithm of [Aldi, de Beaudrap, Gharibian, Saeedi 2021] to solve new instances of QSAT efficiently on qudits. The second of these, in particular, allows us to define the first "quantum-inspired" subclass of TFNP, for which we show QSAT with SDR is complete. Thus, we obtain the first evidence that QSAT with SDR is, in fact, intractable.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite being a classical complexity class, however, TFNP has made a surprise appearance in the study of Quantum Satisfiability (QSAT): If a QSAT instance has a System of Distinct Representatives (SDR), then it has a product-state solution [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Efficiently finding this product-state solution, however, has remained elusive. In this work, we introduce a new framework based on Weighted SDRs (WSDR), which among other results, allows us to: (1) significantly simplify and extend the results of [LLMSS 2010] to qudit systems, (2) establish a connection to the Bézout number for multihomogeneous polynomial systems, and (3) apply the parameterized algorithm of [Aldi, de Beaudrap, Gharibian, Saeedi 2021] to solve new instances of QSAT efficiently on qudits. The second of these, in particular, allows us to define the first "quantum-inspired" subclass of TFNP, for which we show QSAT with SDR is complete. Thus, we obtain the first evidence that QSAT with SDR is, in fact, intractable.
306.
Ruge Lin, Weiqiang Wen
Quantum computation capability verification protocol for noisy intermediate-scale quantum devices with the dihedral coset problem Poster
2023.
@Poster{P1120,
title = {Quantum computation capability verification protocol for noisy intermediate-scale quantum devices with the dihedral coset problem},
author = {Ruge Lin and Weiqiang Wen},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
307.
Nicholas Rubin, Dominic Berry, Alina Kononov, Fionn Malone, Tanuj Khattar, Alec White, Joonho Lee, Hartmut Neven, Ryan Babbush, Andrew Baczewski
Quantum computation of stopping power for inertial fusion target design Talk
2024.
@Talk{T24_124,
title = {Quantum computation of stopping power for inertial fusion target design},
author = {Nicholas Rubin and Dominic Berry and Alina Kononov and Fionn Malone and Tanuj Khattar and Alec White and Joonho Lee and Hartmut Neven and Ryan Babbush and Andrew Baczewski},
year = {2024},
date = {2024-01-01},
abstract = {Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it – one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it – one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.
308.
Sagar Silva Pratapsi, Lorenzo Buffoni, Stefano Gherardini
Quantum Computing Fidelity and Energetics in Driven Quantum Systems Poster
2023.
@Poster{P6503,
title = {Quantum Computing Fidelity and Energetics in Driven Quantum Systems},
author = {Sagar Silva Pratapsi and Lorenzo Buffoni and Stefano Gherardini},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
309.
Yukun Zhang, Yifei Huang, Jinzhao Sun, Dingshun Lv, Xiao Yuan
Quantum Computing Quantum Monte Carlo Poster
2023.
@Poster{P9322,
title = {Quantum Computing Quantum Monte Carlo},
author = {Yukun Zhang and Yifei Huang and Jinzhao Sun and Dingshun Lv and Xiao Yuan},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
310.
Shrigyan Brahmachari, Josep Lumbreras, Marco Tomamichel
Quantum contextual bandits and recommender systems for quantum data Poster
2023.
Abstract | Links:
@Poster{P4568,
title = {Quantum contextual bandits and recommender systems for quantum data},
author = {Shrigyan Brahmachari and Josep Lumbreras and Marco Tomamichel},
url = {https://arxiv.org/abs/2301.13524},
year = {2023},
date = {2023-01-01},
abstract = {We study a recommender system for quantum data using the linear contextual bandit framework. In each round, a learner receives an observable (the context) and has to recommend from a finite set of unknown quantum states (the actions) which one to measure. The learner has the goal of maximizing the reward in each round, that is the outcome of the measurement on the unknown state. Using this model we formulate the low energy quantum state recommendation problem where the context is a Hamiltonian and the goal is to recommend the state with the lowest energy. For this task, we study two families of contexts: the Ising model and a generalized cluster model. We observe that if we interpret the actions as different phases of the models then the recommendation is done by classifying the correct phase of the given Hamiltonian and the strategy can be interpreted as an online quantum phase classifier.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
We study a recommender system for quantum data using the linear contextual bandit framework. In each round, a learner receives an observable (the context) and has to recommend from a finite set of unknown quantum states (the actions) which one to measure. The learner has the goal of maximizing the reward in each round, that is the outcome of the measurement on the unknown state. Using this model we formulate the low energy quantum state recommendation problem where the context is a Hamiltonian and the goal is to recommend the state with the lowest energy. For this task, we study two families of contexts: the Ising model and a generalized cluster model. We observe that if we interpret the actions as different phases of the models then the recommendation is done by classifying the correct phase of the given Hamiltonian and the strategy can be interpreted as an online quantum phase classifier.
311.
Kai-Siang Chen, Gelo Noel M Tabia, Chellasamy Jebarathinam, Shiladitya Mal, Jun-Yi Wu, Yeong-Cherng Liang
Quantum correlations on the no-signaling boundary: self-testing and more Poster
2023.
@Poster{P9103,
title = {Quantum correlations on the no-signaling boundary: self-testing and more},
author = {Kai-Siang Chen and Gelo Noel M Tabia and Chellasamy Jebarathinam and Shiladitya Mal and Jun-Yi Wu and Yeong-Cherng Liang},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688306781-poster-Poster_TQC23_Shiladitya.pdf},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
312.
Anne Broadbent, Arthur Mehta, Yuming Zhao
Quantum delegation with an off-the-shelf device Talk
2024.
@Talk{T24_121,
title = {Quantum delegation with an off-the-shelf device},
author = {Anne Broadbent and Arthur Mehta and Yuming Zhao},
year = {2024},
date = {2024-01-01},
abstract = {Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.
313.
Christopher Chubb, Kamil Korzekwa, Marco Tomamichel, Joseph M. Renes, Patryk Lipka-Bartosik
Quantum dichotomies and coherent thermodynamics beyond first-order asymptotics Poster
2023.
@Poster{P3942,
title = {Quantum dichotomies and coherent thermodynamics beyond first-order asymptotics},
author = {Christopher Chubb and Kamil Korzekwa and Marco Tomamichel and Joseph M. Renes and Patryk Lipka-Bartosik},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
314.
Benjamin Schiffer, Jordi Tura Brugués
Quantum eigenstate broadcasting assisted by a coherent link Poster
2023.
@Poster{P8455,
title = {Quantum eigenstate broadcasting assisted by a coherent link},
author = {Benjamin Schiffer and Jordi Tura Brugués},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
315.
Nunzia Cerrato, Giacomo De Palma, Vittorio Giovannetti
Quantum Entanglement Survival Time in the Presence of Markovian Noise: a Statistical Analysis Poster
2023.
@Poster{P7970,
title = {Quantum Entanglement Survival Time in the Presence of Markovian Noise: a Statistical Analysis},
author = {Nunzia Cerrato and Giacomo De Palma and Vittorio Giovannetti},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
316.
Diogo Cruz, Francisco Monteiro, Bruno Coutinho
Quantum Error Correction via Noise Guessing Decoding Poster
2023.
Abstract | Links:
@Poster{P5281,
title = {Quantum Error Correction via Noise Guessing Decoding},
author = {Diogo Cruz and Francisco Monteiro and Bruno Coutinho},
url = {https://arxiv.org/abs/2208.02744},
year = {2023},
date = {2023-01-01},
abstract = {We present a novel method of quantum error correction, dubbed QGRAND, and analyze its performance for the Pauli noise model. The decoding is adapted from a classical technique called guessing random additive noise decoding (GRAND), which works well for low entropy noise. This decoding process is agnostic to the encoding chosen, enabling us to use quantum random linear codes for the encoding step, which are known to be near-capacity achieving.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
We present a novel method of quantum error correction, dubbed QGRAND, and analyze its performance for the Pauli noise model. The decoding is adapted from a classical technique called guessing random additive noise decoding (GRAND), which works well for low entropy noise. This decoding process is agnostic to the encoding chosen, enabling us to use quantum random linear codes for the encoding step, which are known to be near-capacity achieving.
317.
Nilton Filho, Taketoshi Iyota
Quantum Gate Optimization for Low-level Classical Simulation Poster
2023.
@Poster{P1533,
title = {Quantum Gate Optimization for Low-level Classical Simulation},
author = {Nilton Filho and Taketoshi Iyota},
year = {2023},
date = {2023-01-01},
abstract = {Simulating quantum computation on a classical computer has many applications, including verification of quantum algorithms and design tools for quantum algorithms.
In this research, we design an architecture of classical hardware specifically for simulating quantum computation, and optimize the quantum circuits that run on the architecture to achieve faster simulations than in previous research. The internal architecture aims to improve efficiency of resource use by optimizing the feasibility and cost of general computations. We also implement the designed architecture on a commercial FPGA device and implement several quantum algorithms to evaluate the performance of our architecture, while discussing about feasible limits for quantum computer simulation on classical computers.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Simulating quantum computation on a classical computer has many applications, including verification of quantum algorithms and design tools for quantum algorithms.
In this research, we design an architecture of classical hardware specifically for simulating quantum computation, and optimize the quantum circuits that run on the architecture to achieve faster simulations than in previous research. The internal architecture aims to improve efficiency of resource use by optimizing the feasibility and cost of general computations. We also implement the designed architecture on a commercial FPGA device and implement several quantum algorithms to evaluate the performance of our architecture, while discussing about feasible limits for quantum computer simulation on classical computers.
In this research, we design an architecture of classical hardware specifically for simulating quantum computation, and optimize the quantum circuits that run on the architecture to achieve faster simulations than in previous research. The internal architecture aims to improve efficiency of resource use by optimizing the feasibility and cost of general computations. We also implement the designed architecture on a commercial FPGA device and implement several quantum algorithms to evaluate the performance of our architecture, while discussing about feasible limits for quantum computer simulation on classical computers.
318.
Minki Hhan, Takashi Yamakawa, Aaram Yun
Quantum Generic Hardness for Discrete Logarithms and Integer Factorization Talk
2024.
@Talk{T24_68,
title = {Quantum Generic Hardness for Discrete Logarithms and Integer Factorization},
author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},
year = {2024},
date = {2024-01-01},
abstract = {We study the quantum computational complexity of the discrete logarithm (DL) problems and integer factorization in the context of ``generic algorithms''—that is, algorithms that do not exploit any properties of the group/ring encoding. We establish the generic models of quantum algorithms for group/ring problems as quantum analogs of their classical counterparts. In these models, we count the number of group/ring operations as complexity measures. Shor's and Regev's algorithms (or their slight modifications) can be described in these models. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and integer factorization in these models. * (The DL problem, fully quantum setting) We prove that any generic quantum DL algorithm must make a logarithmic number of group operations for the group size, showing that Shor's algorithm that makes the logarithmic number of group operations is asymptotically optimal regarding the number of group operations. This holds even considering parallel quantum algorithms. * (The DL problem, hybrid/memory-bounded setting) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We establish a model for generic hybrid quantum-classical algorithms and prove the matching lower bounds. We also study the memory-bounded setting and establish asymptotically tight lower bounds. We extend these results to the multiple-instance DL problem with a matching new algorithm. * (Integer factorization) We give a logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also prove a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We study the quantum computational complexity of the discrete logarithm (DL) problems and integer factorization in the context of ``generic algorithms''—that is, algorithms that do not exploit any properties of the group/ring encoding. We establish the generic models of quantum algorithms for group/ring problems as quantum analogs of their classical counterparts. In these models, we count the number of group/ring operations as complexity measures. Shor's and Regev's algorithms (or their slight modifications) can be described in these models. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and integer factorization in these models. * (The DL problem, fully quantum setting) We prove that any generic quantum DL algorithm must make a logarithmic number of group operations for the group size, showing that Shor's algorithm that makes the logarithmic number of group operations is asymptotically optimal regarding the number of group operations. This holds even considering parallel quantum algorithms. * (The DL problem, hybrid/memory-bounded setting) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We establish a model for generic hybrid quantum-classical algorithms and prove the matching lower bounds. We also study the memory-bounded setting and establish asymptotically tight lower bounds. We extend these results to the multiple-instance DL problem with a matching new algorithm. * (Integer factorization) We give a logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also prove a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.
319.
Mateus Araújo, Marcus Huber, Miguel Navascués, Matej Pivoluska, Armin Tavakoli
Quantum key distribution rates from semidefinite programming Poster
2023.
@Poster{P2819,
title = {Quantum key distribution rates from semidefinite programming},
author = {Mateus Araújo and Marcus Huber and Miguel Navascués and Matej Pivoluska and Armin Tavakoli},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
320.
William Kretschmer
Quantum Mass Production Theorems Conference
2023.
Abstract | Links:
@Conference{T6465,
title = {Quantum Mass Production Theorems},
author = {William Kretschmer},
url = {https://arxiv.org/abs/2212.14399},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We prove that for any $n$-qubit unitary transformation $U$ and for any $r = 2^o(n / łog n)$, there exists a quantum circuit to implement $U^øtimes r$ with at most $O(4^n)$ gates. This asymptotically equals the number of gates needed to implement just a single copy of a worst-case $U$. We also establish analogous results for quantum states and diagonal unitary transformations. Our techniques are based on the work of Uhlig [Math. Notes 1974], who proved a similar mass production theorem for Boolean functions.},
howpublished = {Talk and Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {Conference}
}
We prove that for any $n$-qubit unitary transformation $U$ and for any $r = 2^o(n / łog n)$, there exists a quantum circuit to implement $U^øtimes r$ with at most $O(4^n)$ gates. This asymptotically equals the number of gates needed to implement just a single copy of a worst-case $U$. We also establish analogous results for quantum states and diagonal unitary transformations. Our techniques are based on the work of Uhlig [Math. Notes 1974], who proved a similar mass production theorem for Boolean functions.
321.
Vincent Steffan, Fulvio Gesmundo, Vladimir Lysikov
Quantum max-flow in the bridge graph Poster
2023.
@Poster{P1004,
title = {Quantum max-flow in the bridge graph},
author = {Vincent Steffan and Fulvio Gesmundo and Vladimir Lysikov},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
322.
Afham, Richard Kueng, Chris Ferrie
Quantum mean states are nicer than you think: fast algorithms to compute states maximizing average fidelity Poster
2023.
@Poster{P9847,
title = {Quantum mean states are nicer than you think: fast algorithms to compute states maximizing average fidelity},
author = {Afham and Richard Kueng and Chris Ferrie},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
323.
Liubov Markovich, Attaallah Almasi, Sina Zeytinoglu, Johannes Borregaard
Quantum memory assisted observable estimation Poster
2023.
@Poster{P7800,
title = {Quantum memory assisted observable estimation},
author = {Liubov Markovich and Attaallah Almasi and Sina Zeytinoglu and Johannes Borregaard},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
324.
Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto
Quantum Merlin-Arthur proof systems for synthesizing quantum states Poster
2023.
@Poster{P5024,
title = {Quantum Merlin-Arthur proof systems for synthesizing quantum states},
author = {Hugo Delavenne and François Le Gall and Yupan Liu and Masayuki Miyamoto},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
325.
Myeongjin Shin, Junseo Lee, Kabgyun Jeong
Quantum Neural Network Approach to Measuring Von Neumann Entropy Poster
2023.
@Poster{P4953,
title = {Quantum Neural Network Approach to Measuring Von Neumann Entropy},
author = {Myeongjin Shin and Junseo Lee and Kabgyun Jeong},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
326.
Jiachen Hu, Tongyang Li, Xinzhao Wang, Yecheng Xue, Chenyi Zhang, Han Zhong
Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits Talk
2024.
@Talk{T24_281,
title = {Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits},
author = {Jiachen Hu and Tongyang Li and Xinzhao Wang and Yecheng Xue and Chenyi Zhang and Han Zhong},
year = {2024},
date = {2024-01-01},
abstract = {We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.
327.
Jordi Weggemans, Jonas Helsen, Harry Buhrman
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians Talk
2024.
@Talk{T24_218,
title = {Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians},
author = {Jordi Weggemans and Jonas Helsen and Harry Buhrman},
year = {2024},
date = {2024-01-01},
abstract = {We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: - Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply emphuniformly at random, as long as it is allowed to do quantum pre-processing based on the input, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). - If the $q$-local Hamiltonian problem with constant promise gap can be solved in $QCMA$, then $QPCP[q] subseteq QCMA$ for any $q ın mO(1)$. - If $QMA(k)$ has a quantum PCP for any $k łeq poly(n)$, then $QMA(2) = QMA$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: - Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply emphuniformly at random, as long as it is allowed to do quantum pre-processing based on the input, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). - If the $q$-local Hamiltonian problem with constant promise gap can be solved in $QCMA$, then $QPCP[q] subseteq QCMA$ for any $q ın mO(1)$. - If $QMA(k)$ has a quantum PCP for any $k łeq poly(n)$, then $QMA(2) = QMA$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.
328.
Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, Vedran Dunjko
Quantum policy gradient algorithms Conference
2023.
Abstract | Links:
@Conference{T8953,
title = {Quantum policy gradient algorithms},
author = {Sofiene Jerbi and Arjan Cornelissen and Maris Ozols and Vedran Dunjko},
url = {https://arxiv.org/abs/2212.09328},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.},
howpublished = {Talk and Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {Conference}
}
Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.
329.
Ansis Rosmanis
Quantum PRP/PRF Switching Lemma via Adversary Method Poster
2023.
@Poster{P8786,
title = {Quantum PRP/PRF Switching Lemma via Adversary Method},
author = {Ansis Rosmanis},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1687781638-poster-8786.pdf},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
330.
Marco Sciorilli, Lucas Borges, Taylor L. Patti, Giancarlo Camilo, Diego Garcia-Martin, Leandro Aolita
Quantum QUBO solvers with quadratically fewer qubits through multi-basis encoding Poster
2023.
@Poster{P1194,
title = {Quantum QUBO solvers with quadratically fewer qubits through multi-basis encoding},
author = {Marco Sciorilli and Lucas Borges and Taylor L. Patti and Giancarlo Camilo and Diego Garcia-Martin and Leandro Aolita},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
331.
Minseong Kim
Quantum reduction of the Hamiltonian path problem to period-finding Poster
2023.
@Poster{P7933,
title = {Quantum reduction of the Hamiltonian path problem to period-finding},
author = {Minseong Kim},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
332.
Hayata Yamasaki, Sathyawageeswar Subramanian, Satoshi Hayakawa, Sho Sonoda
Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation Poster
2023.
@Poster{P5798,
title = {Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation},
author = {Hayata Yamasaki and Sathyawageeswar Subramanian and Satoshi Hayakawa and Sho Sonoda},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
333.
Ryan Babbush, William Huggins, Dominic Berry, Shu Fay Ung, Andrew Zhao, David Reichman, Hartmut Neven, Andrew Baczewski, Joonho Lee
Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods Poster
2023.
@Poster{P7701,
title = {Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods},
author = {Ryan Babbush and William Huggins and Dominic Berry and Shu Fay Ung and Andrew Zhao and David Reichman and Hartmut Neven and Andrew Baczewski and Joonho Lee},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
334.
Ugnė Liaubaitė, Sabhayata Gupta, Younes Javanmard, Luis Santos, Tobias J. Osborne
Quantum Simulation of Quantum Link Models Poster
2023.
@Poster{P8554,
title = {Quantum Simulation of Quantum Link Models},
author = {Ugnė Liaubaitė and Sabhayata Gupta and Younes Javanmard and Luis Santos and Tobias J. Osborne},
year = {2023},
date = {2023-01-01},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
335.
Frank Somhorst, Reinier Meer, Malaquias Correa Anguita, Riko Schadow, Henk Snijders, Michiel Goede, Ben Kassenberg, Pim Venderbosch, Caterina Taballione, Jorn Epping, Hans Vlekkert, Jardi Timmerhuis, Jacob Bulmer, Jasleen Lugani, Ian Walmsley, P. W. H. Pinkse, Jens Eisert, Nathan Walk, Jelmer Renema
Quantum simulation of thermodynamics in an integrated quantum photonic processor Poster
2023.
@Poster{P3478,
title = {Quantum simulation of thermodynamics in an integrated quantum photonic processor},
author = {Frank Somhorst and Reinier Meer and Malaquias Correa Anguita and Riko Schadow and Henk Snijders and Michiel Goede and Ben Kassenberg and Pim Venderbosch and Caterina Taballione and Jorn Epping and Hans Vlekkert and Jardi Timmerhuis and Jacob Bulmer and Jasleen Lugani and Ian Walmsley and P. W. H. Pinkse and Jens Eisert and Nathan Walk and Jelmer Renema},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
336.
Yuanye Zhu
Quantum solving algorithm for d’Alembert solutions of the wave equation Poster
2023.
@Poster{P7995,
title = {Quantum solving algorithm for d’Alembert solutions of the wave equation},
author = {Yuanye Zhu},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
337.
Shubham P. Jain, Joseph T. Iosue, Alexander Barg, Victor V. Albert
Quantum Spherical Codes Talk
2024.
@Talk{T24_354,
title = {Quantum Spherical Codes},
author = {Shubham P. Jain and Joseph T. Iosue and Alexander Barg and Victor V. Albert},
year = {2024},
date = {2024-01-01},
abstract = {We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise.
338.
Nai-Hui Chia, Daniel Liang, Fang Song
Quantum State Learning Implies Circuit Lower Bounds Talk
2024.
@Talk{T24_348,
title = {Quantum State Learning Implies Circuit Lower Bounds},
author = {Nai-Hui Chia and Daniel Liang and Fang Song},
year = {2024},
date = {2024-01-01},
abstract = {We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^n^2) time and 2^n^0.99 samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^n^2)-time and 2^n^0.99-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^n^2) time and 2^n^0.99 samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^n^2)-time and 2^n^0.99-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.
339.
Xiao-Ming Zhang, Tongyang Li, Xiao Yuan
Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications Poster
2023.
Abstract | Links:
@Poster{P2403,
title = {Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications},
author = {Xiao-Ming Zhang and Tongyang Li and Xiao Yuan},
url = {https://arxiv.org/abs/2201.11495 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1683015338-poster-2403.pdf},
year = {2023},
date = {2023-01-01},
abstract = {Quantum state preparation is an important subroutine for quantum computing. We show that any $n$-qubit quantum state can be prepared with a $Theta(n)$-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with $dgeqslant2$ non-zero entries, we can reduce the circuit depth to $Theta(łog(nd))$ with $O(ndłog d)$ ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Quantum state preparation is an important subroutine for quantum computing. We show that any $n$-qubit quantum state can be prepared with a $Theta(n)$-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with $dgeqslant2$ non-zero entries, we can reduce the circuit depth to $Theta(łog(nd))$ with $O(ndłog d)$ ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.
340.
Yupan Liu
Quantum state testing beyond the polarizing regime and quantum triangular discrimination Poster
2023.
@Poster{P9117,
title = {Quantum state testing beyond the polarizing regime and quantum triangular discrimination},
author = {Yupan Liu},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
341.
Francesco Anna Mele, Salvatore F. E. Oliviero, Lennart Bittel, Jens Eisert, Vittorio Giovannetti, Ludovico Lami, Lorenzo Leone, Antonio Anna Mele
Quantum state tomography of continuous variable systems Talk
2024.
@Talk{T24_237,
title = {Quantum state tomography of continuous variable systems},
author = {Francesco Anna Mele and Salvatore F. E. Oliviero and Lennart Bittel and Jens Eisert and Vittorio Giovannetti and Ludovico Lami and Lorenzo Leone and Antonio Anna Mele},
year = {2024},
date = {2024-01-01},
abstract = {While quantum state tomography has been extensively analysed for qubit and qudit systems, rigorous performance guarantees in terms of ε-approximation in trace distance remain largely unexplored for continuous variable quantum systems, due to subtleties that arise in the infinite-dimensional context. This work addresses this gap. First, we discover that to learn energy-constrained n-mode states, the sample complexity must scale with ε as Ω(1/ε^(2n)). This is in sharp contrast with the n-qubit case, where the ε-scaling is O(1/ε^2) — thereby establishing the extreme inefficiency of continuous variable tomography. Remarkably, we prove that O(1/ε^(2n)) copies are both necessary and sufficient if we restrict to tomography of pure states. Second, we establish that Gaussian states can be efficiently learned, a result that has been previously assumed but never rigorously proved. To do that, we answer the following fundamental question for Gaussian quantum information: If we approximate the first moment and covariance matrix of an unknown Gaussian state with precision ε, what is the resulting trace distance error on the state? Third, we show how to efficiently learn states prepared by Gaussian unitaries and a few local non-Gaussian evolutions, unveiling more on the structure of these slightly non-Gaussian systems.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
While quantum state tomography has been extensively analysed for qubit and qudit systems, rigorous performance guarantees in terms of ε-approximation in trace distance remain largely unexplored for continuous variable quantum systems, due to subtleties that arise in the infinite-dimensional context. This work addresses this gap. First, we discover that to learn energy-constrained n-mode states, the sample complexity must scale with ε as Ω(1/ε^(2n)). This is in sharp contrast with the n-qubit case, where the ε-scaling is O(1/ε^2) — thereby establishing the extreme inefficiency of continuous variable tomography. Remarkably, we prove that O(1/ε^(2n)) copies are both necessary and sufficient if we restrict to tomography of pure states. Second, we establish that Gaussian states can be efficiently learned, a result that has been previously assumed but never rigorously proved. To do that, we answer the following fundamental question for Gaussian quantum information: If we approximate the first moment and covariance matrix of an unknown Gaussian state with precision ε, what is the resulting trace distance error on the state? Third, we show how to efficiently learn states prepared by Gaussian unitaries and a few local non-Gaussian evolutions, unveiling more on the structure of these slightly non-Gaussian systems.
342.
Ming-Chien Hsu, En-Jui Kuo, Wei-Hsuan Yu, Jian-Feng Cai, Min-Hsiu Hsieh
Quantum state tomography via non-convex Riemannian gradient descent Poster
2023.
@Poster{P2471,
title = {Quantum state tomography via non-convex Riemannian gradient descent},
author = {Ming-Chien Hsu and En-Jui Kuo and Wei-Hsuan Yu and Jian-Feng Cai and Min-Hsiu Hsieh},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688135521-poster-poster_2471_Quantum-state-tomography-via-non-convex-Riemannian-gradient-descent.pdf},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
343.
Matt Wilson, Giulio Chiribella, Aleks Kissinger
Quantum Supermaps are Characterised by Locality Poster
2023.
@Poster{P7367,
title = {Quantum Supermaps are Characterised by Locality},
author = {Matt Wilson and Giulio Chiribella and Aleks Kissinger},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
344.
David Trillo, Thinh Le, Miguel Navascues
Quantum supremacy in mechanical tasks: projectiles, rockets and quantum backflow Workshop
2023.
Abstract | Links:
@Workshop{T5145,
title = {Quantum supremacy in mechanical tasks: projectiles, rockets and quantum backflow},
author = {David Trillo and Thinh Le and Miguel Navascues},
url = {https://arxiv.org/abs/2209.00725},
year = {2023},
date = {2023-01-01},
abstract = {We consider a non-relativistic quantum particle in an infinite line. We estimate the maximum probability of finding the particle at some distant position given that it is initially bound in some region. We prove that quantum mechanics allows for greater probabilities than classical mechanics - thus obtaining a new kind of quantum advantage. We show that this effect is mathematically related to quantum backflow, and use this to improve the upper bounds on the Bracken-Mellow constant. Several generalizations are studied.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
We consider a non-relativistic quantum particle in an infinite line. We estimate the maximum probability of finding the particle at some distant position given that it is initially bound in some region. We prove that quantum mechanics allows for greater probabilities than classical mechanics - thus obtaining a new kind of quantum advantage. We show that this effect is mathematically related to quantum backflow, and use this to improve the upper bounds on the Bracken-Mellow constant. Several generalizations are studied.
345.
Marco Fanizza, Josep Lumbreras, Andreas Winter
Quantum theory in finite dimension cannot explain every general process with finite memory Workshop
2023.
Abstract | Links:
@Workshop{T4004,
title = {Quantum theory in finite dimension cannot explain every general process with finite memory},
author = {Marco Fanizza and Josep Lumbreras and Andreas Winter},
url = {https://arxiv.org/abs/2209.11225 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688151704-video-4004tqc2023.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory state is a finite dimensional quantum state, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory state is a finite dimensional quantum state, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.
346.
Stefano Chessa, Salvatore Tirone, Raffaele Salvia, Vittorio Giovannetti
Quantum Work Capacitances of quantum channels Poster
2023.
@Poster{P687,
title = {Quantum Work Capacitances of quantum channels},
author = {Stefano Chessa and Salvatore Tirone and Raffaele Salvia and Vittorio Giovannetti},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
347.
Samson Wang, Sam McArdle, Mario Berta
Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra Workshop
2023.
Abstract | Links:
@Workshop{T1887,
title = {Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra},
author = {Samson Wang and Sam McArdle and Mario Berta},
url = {https://arxiv.org/abs/2302.01873},
year = {2023},
date = {2023-01-01},
abstract = {We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. For $N times N$ Hermitian matrices, the space cost is $łog(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. For $N times N$ Hermitian matrices, the space cost is $łog(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.
348.
Yixu Wang, Yijia Xu, En-Jui Kuo, Victor V. Albert
Qubit-oscillator concatenated codes: decoding formalism & code comparison Poster
2023.
@Poster{P8276,
title = {Qubit-oscillator concatenated codes: decoding formalism & code comparison},
author = {Yixu Wang and Yijia Xu and En-Jui Kuo and Victor V. Albert},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
349.
Jonas Haferkamp
Random quantum circuits are approximate unitary $t$-designs in depth $Ołeft(nt^5+o(1)right)$ Poster
2023.
@Poster{P2475,
title = {Random quantum circuits are approximate unitary $t$-designs in depth $Ołeft(nt^5+o(1)right)$},
author = {Jonas Haferkamp},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
350.
Newton Cheng, Cécilia Lancien, Geoff Penington, Michael Walter, Freek Witteveen
Random Tensor Networks with Nontrivial Links Poster
2023.
@Poster{P8176,
title = {Random Tensor Networks with Nontrivial Links},
author = {Newton Cheng and Cécilia Lancien and Geoff Penington and Michael Walter and Freek Witteveen},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
351.
Vishnu Iyer, Siddhartha Jain, Vinayak Kumar, Michael Whitmeyer
Rational Degree, Postselection, and Bounded-Error Quantum Computation Poster
2023.
@Poster{P229,
title = {Rational Degree, Postselection, and Bounded-Error Quantum Computation},
author = {Vishnu Iyer and Siddhartha Jain and Vinayak Kumar and Michael Whitmeyer},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
352.
Anastasiia Nikolaeva, Evgeniy Kiktenko, Aleksey Fedorov
Realizing quantum algorithms on qubits embedded into trapped-ion qudits Poster
2023.
@Poster{P9010,
title = {Realizing quantum algorithms on qubits embedded into trapped-ion qudits},
author = {Anastasiia Nikolaeva and Evgeniy Kiktenko and Aleksey Fedorov},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688366691-poster-9010.pdf},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
353.
Mathieu Bérubé-Vallières, Noah Brüstle, Claude Crépeau
Reductions among Magic Rectangle Games Poster
2023.
@Poster{P3108,
title = {Reductions among Magic Rectangle Games},
author = {Mathieu Bérubé-Vallières and Noah Brüstle and Claude Crépeau},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
354.
Felix Huber, Nikolai Wyderka
Refuting spectral compatibility of quantum marginals Workshop
2023.
Abstract | Links:
@Workshop{T9488,
title = {Refuting spectral compatibility of quantum marginals},
author = {Felix Huber and Nikolai Wyderka},
url = {https://arxiv.org/abs/2211.06349},
year = {2023},
date = {2023-01-01},
abstract = {The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry-reduced semidefinite programming hierarchy for detecting incompatible spectra. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension-free, certifying incompatibility in all local dimensions. The hierarchy equally applies to the sums of Hermitian matrices problem, to optimize trace polynomials on the positive cone, to the compatibility of invariants, and to certify vanishing Kronecker coefficients.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry-reduced semidefinite programming hierarchy for detecting incompatible spectra. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension-free, certifying incompatibility in all local dimensions. The hierarchy equally applies to the sums of Hermitian matrices problem, to optimize trace polynomials on the positive cone, to the compatibility of invariants, and to certify vanishing Kronecker coefficients.
355.
Fulvio Flamini, Marius Krumm, Lukas J. Fiderer, Thomas Mueller, Hans J. Briegel
Reinforcement learning and decision making via single-photon quantum walks Poster
2023.
@Poster{P8047,
title = {Reinforcement learning and decision making via single-photon quantum walks},
author = {Fulvio Flamini and Marius Krumm and Lukas J. Fiderer and Thomas Mueller and Hans J. Briegel},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
356.
Julius Wallnöfer, Frederik Hahn, Fabian Wiesner, Nathan Walk, Jens Eisert
ReQuSim: Faithfully simulating near-term quantum repeaters Poster
2023.
@Poster{P9247,
title = {ReQuSim: Faithfully simulating near-term quantum repeaters},
author = {Julius Wallnöfer and Frederik Hahn and Fabian Wiesner and Nathan Walk and Jens Eisert},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
357.
Luís Bugalho, Emmanuel Zambrini Cruzeiro, Kevin Chen, Wenhan Dai, Dirk Englund, Yasser Omar
Resource-efficient simulation of noisy quantum circuits and application to network-enabled QRAM optimization Poster
2023.
@Poster{P9470,
title = {Resource-efficient simulation of noisy quantum circuits and application to network-enabled QRAM optimization},
author = {Luís Bugalho and Emmanuel Zambrini Cruzeiro and Kevin Chen and Wenhan Dai and Dirk Englund and Yasser Omar},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
358.
Ulysse Chabaud, Mattia Walschaers
Resources for bosonic quantum computational advantage Workshop
2023.
Abstract | Links:
@Workshop{T6568,
title = {Resources for bosonic quantum computational advantage},
author = {Ulysse Chabaud and Mattia Walschaers},
url = {https://arxiv.org/abs/2207.11781},
year = {2023},
date = {2023-01-01},
abstract = {Quantum computers promise to dramatically outperform their classical counterparts. However, the non-classical resources enabling such computational advantages are challenging to pinpoint, as it is not a single resource but the subtle interplay of many that can be held responsible for these potential advantages. In this work, we show that every bosonic quantum computation can be recast into a continuous-variable sampling computation where all computational resources are contained in the input state. Using this reduction, we derive a general classical algorithm for the strong simulation of bosonic computations, whose complexity scales with the non-Gaussian stellar rank of both the input state and the measurement setup. We further study the conditions for an efficient classical simulation of the associated continuous-variable sampling computations and identify an operational notion of non-Gaussian entanglement based on the lack of passive separability, thus clarifying the interplay of bosonic quantum computational resources such as squeezing, non-Gaussianity and entanglement.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
Quantum computers promise to dramatically outperform their classical counterparts. However, the non-classical resources enabling such computational advantages are challenging to pinpoint, as it is not a single resource but the subtle interplay of many that can be held responsible for these potential advantages. In this work, we show that every bosonic quantum computation can be recast into a continuous-variable sampling computation where all computational resources are contained in the input state. Using this reduction, we derive a general classical algorithm for the strong simulation of bosonic computations, whose complexity scales with the non-Gaussian stellar rank of both the input state and the measurement setup. We further study the conditions for an efficient classical simulation of the associated continuous-variable sampling computations and identify an operational notion of non-Gaussian entanglement based on the lack of passive separability, thus clarifying the interplay of bosonic quantum computational resources such as squeezing, non-Gaussianity and entanglement.
359.
Kyrylo Simonov, Giulio Chiribella
Revealing non-classicality with indefinite causal orders Poster
2023.
@Poster{P3844,
title = {Revealing non-classicality with indefinite causal orders},
author = {Kyrylo Simonov and Giulio Chiribella},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
360.
Jeremiah Blocki, Blake Holman, Seunghoon Lee
Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity Talk
2024.
@Talk{T24_243,
title = {Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity},
author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee},
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 = {},
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.
