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.
181.
Rafael Wagner, Rui Soares Barbosa, Ernesto Galvao
Inequalities witnessing coherence, nonlocality, and contextuality Poster
2023.
@Poster{P9629,
title = {Inequalities witnessing coherence, nonlocality, and contextuality},
author = {Rafael Wagner and Rui Soares Barbosa and Ernesto Galvao},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
182.
Francisco Escudero Gutiérrez
Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms Workshop
2023.
Abstract | Links:
@Workshop{T5976,
title = {Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms},
author = {Francisco Escudero Gutiérrez},
url = {https://arxiv.org/abs/2304.06713},
year = {2023},
date = {2023-01-01},
abstract = {We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.
183.
Lucas Pollyceno, Rafael Chaves, Rafael Rabelo
Information causality in multipartite scenarios Poster
2023.
@Poster{P9232,
title = {Information causality in multipartite scenarios},
author = {Lucas Pollyceno and Rafael Chaves and Rafael Rabelo},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688143466-poster-9232.pdf},
year = {2023},
date = {2023-01-01},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
184.
Matthias C. Caro, Tom Gur, Cambyse Rouze, Daniel Stilck França, Sathyawageeswar Subramanian
Information-theoretic generalization bounds for learning from quantum data Talk
2024.
@Talk{T24_185,
title = {Information-theoretic generalization bounds for learning from quantum data},
author = {Matthias C. Caro and Tom Gur and Cambyse Rouze and Daniel Stilck França and Sathyawageeswar Subramanian},
year = {2024},
date = {2024-01-01},
abstract = {Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the framework of quantum probably approximately correct (PAC) learning, to the recently proposed shadow variants of state tomography. However, the many directions of quantum learning theory have so far evolved separately. We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data and then testing how well the learned hypothesis generalizes to new data. In this framework, we prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum mutual information quantities measuring how strongly the learner's hypothesis depends on the specific data seen during training. To achieve this, we use tools from quantum optimal transport and quantum concentration inequalities to establish non-commutative versions of decoupling lemmas that underlie recent information-theoretic generalization bounds for classical machine learning. Our framework encompasses and gives intuitively accessible generalization bounds for a variety of quantum learning scenarios such as quantum state discrimination, PAC learning quantum states, quantum parameter estimation, and quantumly PAC learning classical functions. Thereby, our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
185.
Islam Faisal
Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation Poster
2023.
@Poster{P2568,
title = {Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation},
author = {Islam Faisal},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
186.
Swati Kumari, Javid Naikoo, Sibasish Ghosh, Alok Pan
Interplay of nonlocality and incompatibility breaking qubit channels Poster
2023.
@Poster{P8808,
title = {Interplay of nonlocality and incompatibility breaking qubit channels},
author = {Swati Kumari and Javid Naikoo and Sibasish Ghosh and Alok Pan},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688272331-poster-8808.pdf},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
187.
Getahun Fikadu, Amit Pandey
Investigating The Effects of Hyperparameters in Quantum Enhanced Deep Reinforcement Learning Poster
2023.
@Poster{P2069,
title = {Investigating The Effects of Hyperparameters in Quantum Enhanced Deep Reinforcement Learning},
author = {Getahun Fikadu and Amit Pandey},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
188.
Michael Bremner, Bin Cheng, Zhengfeng Ji
IQP Sampling and Verifiable Quantum Advantage: Stabilizer Constructions and Classical Security Poster
2023.
@Poster{P2321,
title = {IQP Sampling and Verifiable Quantum Advantage: Stabilizer Constructions and Classical Security},
author = {Michael Bremner and Bin Cheng and Zhengfeng Ji},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
189.
Angela Karanjai, Stephen Bartlett
Kochen-Spekker contextuality as a statistical property that requires non-Markovian modelling Poster
2023.
@Poster{P2503,
title = {Kochen-Spekker contextuality as a statistical property that requires non-Markovian modelling},
author = {Angela Karanjai and Stephen Bartlett},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
190.
Carl Miller, Yusuf Alnawakhtha, Atul Mantri, Daochen Wang
Lattice-Based Quantum Advantage from Rotated Measurements Poster
2023.
@Poster{P7482,
title = {Lattice-Based Quantum Advantage from Rotated Measurements},
author = {Carl Miller and Yusuf Alnawakhtha and Atul Mantri and Daochen Wang},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
191.
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, Carlos Palazuelos
Learning low-degree quantum objects Talk
2024.
@Talk{T24_290,
title = {Learning low-degree quantum objects},
author = {Srinivasan Arunachalam and Arkopal Dutt and Francisco Escudero Gutiérrez and Carlos Palazuelos},
year = {2024},
date = {2024-01-01},
abstract = {We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We consider the problem of learning low-degree quantum objects up to ε-error in l_2-distance. We show the following results: (I) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/ε^d) queries (which is independent of n), (II) polynomials p:-1,1^n -> [-1,1] arising from d-query quantum algorithms can be learned from O((1/ε)^d log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (III) degree-d polynomials p:-1,1^n -> [-1,1] can be learned through O(1/ε^d) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded polynomials.
192.
Janek Denzler, Ellen Derbyshire, Tommaso Guaita, Antonio A. Mele, Jens Eisert
Learning moments of interacting fermionic systems from translationally invariant randomized measurements Poster
2023.
@Poster{P3957,
title = {Learning moments of interacting fermionic systems from translationally invariant randomized measurements},
author = {Janek Denzler and Ellen Derbyshire and Tommaso Guaita and Antonio A. Mele and Jens Eisert},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
193.
Matthias C. Caro
Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix Poster
2023.
@Poster{P4903,
title = {Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix},
author = {Matthias C. Caro},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
194.
Dmytro Bondarenko, Robert Salzmann, Viktoria Schmiesing
Learning Quantum Processes with Memory - Quantum Recurrent Neural Networks Poster
2023.
@Poster{P1244,
title = {Learning Quantum Processes with Memory - Quantum Recurrent Neural Networks},
author = {Dmytro Bondarenko and Robert Salzmann and Viktoria Schmiesing},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
195.
Marco Fanizza, Yihui Quek, Matteo Rosati
Learning quantum processes without input control Poster
2023.
@Poster{P4060,
title = {Learning quantum processes without input control},
author = {Marco Fanizza and Yihui Quek and Matteo Rosati},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
196.
Arthur Strauss
Leveraging Deep Reinforcement Learning for real-time context-aware Gate Calibration Poster
2023.
@Poster{P1588,
title = {Leveraging Deep Reinforcement Learning for real-time context-aware Gate Calibration},
author = {Arthur Strauss},
year = {2023},
date = {2023-01-01},
abstract = {The advent of quantum computers in the near-term prospect induces the need of mitigating various sources of noise that corrupt quantum information, preventing the successful execution of quantum algorithms. While noise characterization in hardware has been the subject of many investigations [1], scaling up the size of quantum systems involves additional noise sources that go beyond what basic noise models can describe. To cope with this issue, many techniques relying on experimental feedback have been used to
build more accurate quantum gate operations [2-5]. However, the considered problems at hand are usually tackled in a static background, in the sense that each gate is calibrated independently of the context it is meant to be used in, such as an algorithm.
For instance, playing a two-qubit gate for two specific qubits of the processor while running other gates on neighboring qubits yields a different gate fidelity from the case where those latter are maintained idle, as a result of non-local crosstalk. To overcome this difficulty, we propose to use model-free reinforcement learning to calibrate gate operations in situ. Reinforcement Learning has proven to be a valuable tool in many quantum tasks [4-8]. We therefore employ this method to calibrate a two-qubit gate directly from experimental data, while ensuring low sampling overhead. We restrict the action space to pulse parameters that can be adjusted in real time, i.e. parameters that are tunable without having to load a new waveform in the control system and therefore without having to recompile the quantum circuit. That way, one can adapt the initial gate calibration based on where (on which qubits) and when (at which time stamp) it is applied in the circuit to mitigate noisy interactions that uniquely define our dynamical system. As the feature of real-time pulse parameter update is enabled by current state-of-the-art control systems [9], we envision our method to stand as a practical calibration subroutine that could lower the usual latency overhead induced
by the need of recompiling the entire adapted waveform which is a common drawback in feedback-based optimal control protocols. We believe this stochastic method would stand as a complementary tool to other optimal control and circuit compilation approaches
for pushing further noise mitigation strategies in a relevant context of quantum algorithms execution.
References:
[1] H.-P. Breuer, F. Petruccione, The Theory of Open Quantum Systems, en. Oxford University Press, 2002
[2] J. Kelly, et al., “Optimal quantum control using randomized
benchmarking”, Physical Review Letters, vol. 112, no. 24, p. 240 504, Jun. 2014
[3] N. Wittler, et al., “Integrated Tool Set for Control, Calibration, and Characterization of Quantum Devices Applied to Superconducting Qubits”, Physical Review Applied, vol.
15, no. 3, p. 034 080, Mar. 2021
[4] Y. Baum, et al., “Experimental Deep Reinforcement Learning for Error-Robust Gate-Set Design on a Superconducting Quantum Computer”, PRX Quantum, vol. 2, no. 4, p. 040 324, Nov. 2021
[5] V. V. Sivak, et al., “Model-Free
Quantum Control with Reinforcement Learning”, Physical Review X, vol. 12, no. 1, p. 011 059, Mar. 2022
[6] Sivak, et al. Real-time quantum error correction beyond break-even. Nature 616, 50–55 (2023)
[7] T. Fösel, P. Tighineanu, T. Weiss, and F. Marquardt,
“Reinforcement Learning with Neural Networks for Quantum Feedback”, Physical Review X, vol. 8, no. 3, p. 031 084, Sep. 2018
[8] K. Reuer, et al., Realizing a deep reinforcement learning agent discovering real-time feedback control strategies for a quantum
system, arXiv:2210.16715 [quant-ph], Oct. 2022 [9] Q. Machines, OPX+ - Universal Quantum Control Hardware, en-US. https://www.quantum-machines.co/opx+/},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
The advent of quantum computers in the near-term prospect induces the need of mitigating various sources of noise that corrupt quantum information, preventing the successful execution of quantum algorithms. While noise characterization in hardware has been the subject of many investigations [1], scaling up the size of quantum systems involves additional noise sources that go beyond what basic noise models can describe. To cope with this issue, many techniques relying on experimental feedback have been used to
build more accurate quantum gate operations [2-5]. However, the considered problems at hand are usually tackled in a static background, in the sense that each gate is calibrated independently of the context it is meant to be used in, such as an algorithm.
For instance, playing a two-qubit gate for two specific qubits of the processor while running other gates on neighboring qubits yields a different gate fidelity from the case where those latter are maintained idle, as a result of non-local crosstalk. To overcome this difficulty, we propose to use model-free reinforcement learning to calibrate gate operations in situ. Reinforcement Learning has proven to be a valuable tool in many quantum tasks [4-8]. We therefore employ this method to calibrate a two-qubit gate directly from experimental data, while ensuring low sampling overhead. We restrict the action space to pulse parameters that can be adjusted in real time, i.e. parameters that are tunable without having to load a new waveform in the control system and therefore without having to recompile the quantum circuit. That way, one can adapt the initial gate calibration based on where (on which qubits) and when (at which time stamp) it is applied in the circuit to mitigate noisy interactions that uniquely define our dynamical system. As the feature of real-time pulse parameter update is enabled by current state-of-the-art control systems [9], we envision our method to stand as a practical calibration subroutine that could lower the usual latency overhead induced
by the need of recompiling the entire adapted waveform which is a common drawback in feedback-based optimal control protocols. We believe this stochastic method would stand as a complementary tool to other optimal control and circuit compilation approaches
for pushing further noise mitigation strategies in a relevant context of quantum algorithms execution.
References:
[1] H.-P. Breuer, F. Petruccione, The Theory of Open Quantum Systems, en. Oxford University Press, 2002
[2] J. Kelly, et al., “Optimal quantum control using randomized
benchmarking”, Physical Review Letters, vol. 112, no. 24, p. 240 504, Jun. 2014
[3] N. Wittler, et al., “Integrated Tool Set for Control, Calibration, and Characterization of Quantum Devices Applied to Superconducting Qubits”, Physical Review Applied, vol.
15, no. 3, p. 034 080, Mar. 2021
[4] Y. Baum, et al., “Experimental Deep Reinforcement Learning for Error-Robust Gate-Set Design on a Superconducting Quantum Computer”, PRX Quantum, vol. 2, no. 4, p. 040 324, Nov. 2021
[5] V. V. Sivak, et al., “Model-Free
Quantum Control with Reinforcement Learning”, Physical Review X, vol. 12, no. 1, p. 011 059, Mar. 2022
[6] Sivak, et al. Real-time quantum error correction beyond break-even. Nature 616, 50–55 (2023)
[7] T. Fösel, P. Tighineanu, T. Weiss, and F. Marquardt,
“Reinforcement Learning with Neural Networks for Quantum Feedback”, Physical Review X, vol. 8, no. 3, p. 031 084, Sep. 2018
[8] K. Reuer, et al., Realizing a deep reinforcement learning agent discovering real-time feedback control strategies for a quantum
system, arXiv:2210.16715 [quant-ph], Oct. 2022 [9] Q. Machines, OPX+ - Universal Quantum Control Hardware, en-US. https://www.quantum-machines.co/opx+/
build more accurate quantum gate operations [2-5]. However, the considered problems at hand are usually tackled in a static background, in the sense that each gate is calibrated independently of the context it is meant to be used in, such as an algorithm.
For instance, playing a two-qubit gate for two specific qubits of the processor while running other gates on neighboring qubits yields a different gate fidelity from the case where those latter are maintained idle, as a result of non-local crosstalk. To overcome this difficulty, we propose to use model-free reinforcement learning to calibrate gate operations in situ. Reinforcement Learning has proven to be a valuable tool in many quantum tasks [4-8]. We therefore employ this method to calibrate a two-qubit gate directly from experimental data, while ensuring low sampling overhead. We restrict the action space to pulse parameters that can be adjusted in real time, i.e. parameters that are tunable without having to load a new waveform in the control system and therefore without having to recompile the quantum circuit. That way, one can adapt the initial gate calibration based on where (on which qubits) and when (at which time stamp) it is applied in the circuit to mitigate noisy interactions that uniquely define our dynamical system. As the feature of real-time pulse parameter update is enabled by current state-of-the-art control systems [9], we envision our method to stand as a practical calibration subroutine that could lower the usual latency overhead induced
by the need of recompiling the entire adapted waveform which is a common drawback in feedback-based optimal control protocols. We believe this stochastic method would stand as a complementary tool to other optimal control and circuit compilation approaches
for pushing further noise mitigation strategies in a relevant context of quantum algorithms execution.
References:
[1] H.-P. Breuer, F. Petruccione, The Theory of Open Quantum Systems, en. Oxford University Press, 2002
[2] J. Kelly, et al., “Optimal quantum control using randomized
benchmarking”, Physical Review Letters, vol. 112, no. 24, p. 240 504, Jun. 2014
[3] N. Wittler, et al., “Integrated Tool Set for Control, Calibration, and Characterization of Quantum Devices Applied to Superconducting Qubits”, Physical Review Applied, vol.
15, no. 3, p. 034 080, Mar. 2021
[4] Y. Baum, et al., “Experimental Deep Reinforcement Learning for Error-Robust Gate-Set Design on a Superconducting Quantum Computer”, PRX Quantum, vol. 2, no. 4, p. 040 324, Nov. 2021
[5] V. V. Sivak, et al., “Model-Free
Quantum Control with Reinforcement Learning”, Physical Review X, vol. 12, no. 1, p. 011 059, Mar. 2022
[6] Sivak, et al. Real-time quantum error correction beyond break-even. Nature 616, 50–55 (2023)
[7] T. Fösel, P. Tighineanu, T. Weiss, and F. Marquardt,
“Reinforcement Learning with Neural Networks for Quantum Feedback”, Physical Review X, vol. 8, no. 3, p. 031 084, Sep. 2018
[8] K. Reuer, et al., Realizing a deep reinforcement learning agent discovering real-time feedback control strategies for a quantum
system, arXiv:2210.16715 [quant-ph], Oct. 2022 [9] Q. Machines, OPX+ - Universal Quantum Control Hardware, en-US. https://www.quantum-machines.co/opx+/
197.
Sisi Zhou
Limits of noisy quantum metrology with restricted quantum controls Talk
2024.
@Talk{T24_81,
title = {Limits of noisy quantum metrology with restricted quantum controls},
author = {Sisi Zhou},
year = {2024},
date = {2024-01-01},
abstract = {The Heisenberg limit (HL) and the standard quantum limit (SQL) are two quantum metrological limits, which describe the scalings of estimation precision $Delta hatþeta$ of an unknown parameter θ with respect to $n$, the number of one-parameter quantum channels applied. It was known that the HL ($Delta hatþeta propto 1/n$) is achievable using quantum error correction (QEC) strategies when the ``Hamiltonian-not-in-Kraus-span'' (HNKS) condition is satisfied; and when HNKS is violated, the SQL ($Delta hatþeta propto 1/n^1/2$) is optimal and can be achieved with $n$ repetitive measurements. However, it is unknown whether such limits are still achievable using restricted quantum devices where the required QEC operations are not available—e.g., finite-size devices where only unitary controls are available or where noiseless ancilla is not available. In this work, we identify various new noisy metrological limits for estimating one-parameter qubit channels in different settings with restricted controls. The HL is proven to be unattainbale in these cases, indicating the necessity of QEC in achieving the HL. Furthermore, we find a necessary and sufficient condition for qubit channels to attain the SQL, called the ``rotation-generators-not-in-Kraus-span'' (RGNKS) condition. When RGNKS is satisfied, the SQL is achievable using only unitary controls and a single measurement. When RGNKS is violated, the estimation precision (in most cases) has a constant floor when repetitive measurements are not allowed. Demonstration of this separation in metrological powers is within reach of current quantum technologies.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
The Heisenberg limit (HL) and the standard quantum limit (SQL) are two quantum metrological limits, which describe the scalings of estimation precision $Delta hatþeta$ of an unknown parameter θ with respect to $n$, the number of one-parameter quantum channels applied. It was known that the HL ($Delta hatþeta propto 1/n$) is achievable using quantum error correction (QEC) strategies when the ``Hamiltonian-not-in-Kraus-span'' (HNKS) condition is satisfied; and when HNKS is violated, the SQL ($Delta hatþeta propto 1/n^1/2$) is optimal and can be achieved with $n$ repetitive measurements. However, it is unknown whether such limits are still achievable using restricted quantum devices where the required QEC operations are not available—e.g., finite-size devices where only unitary controls are available or where noiseless ancilla is not available. In this work, we identify various new noisy metrological limits for estimating one-parameter qubit channels in different settings with restricted controls. The HL is proven to be unattainbale in these cases, indicating the necessity of QEC in achieving the HL. Furthermore, we find a necessary and sufficient condition for qubit channels to attain the SQL, called the ``rotation-generators-not-in-Kraus-span'' (RGNKS) condition. When RGNKS is satisfied, the SQL is achievable using only unitary controls and a single measurement. When RGNKS is violated, the estimation precision (in most cases) has a constant floor when repetitive measurements are not allowed. Demonstration of this separation in metrological powers is within reach of current quantum technologies.
198.
Michael Liaofan Liu, Florian Kanitschar, Amir Arqand, Ernest Y. -Z. Tan
Lipschitz continuity of quantum-classical conditional entropies with respect to angular distance and related properties Poster
2023.
@Poster{P7279,
title = {Lipschitz continuity of quantum-classical conditional entropies with respect to angular distance and related properties},
author = {Michael Liaofan Liu and Florian Kanitschar and Amir Arqand and Ernest Y. -Z. Tan},
year = {2023},
date = {2023-01-01},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
199.
Nolan Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi
Local Hamiltonians with no low-energy stabilizer states Conference
2023.
Abstract | Links:
@Conference{T9486,
title = {Local Hamiltonians with no low-energy stabilizer states},
author = {Nolan Coble and Matthew Coudron and Jon Nelson and Seyed Sajjad Nezhadi},
url = {https://arxiv.org/abs/2302.14755},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228},
howpublished = {Talk and Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {Conference}
}
The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228
200.
Luke Coffman, Graeme Smith, Jacob Beckey
Local measurement strategies for multipartite entanglement quantification Poster
2023.
@Poster{P547,
title = {Local measurement strategies for multipartite entanglement quantification},
author = {Luke Coffman and Graeme Smith and Jacob Beckey},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
201.
Bruna Araújo, Márcio Taddei, Daniel Cavalcanti, Antonio Acín
Local quantum overlapping tomography Poster
2023.
Abstract | Links:
@Poster{P7291,
title = {Local quantum overlapping tomography},
author = {Bruna Araújo and Márcio Taddei and Daniel Cavalcanti and Antonio Acín},
url = {https://arxiv.org/abs/2112.03924},
year = {2023},
date = {2023-01-01},
abstract = {Reconstructing the full quantum state of a many-body system requires the estimation of a number of parameters that grows exponentially with system size. Nevertheless, there are situations in which one is only interested in a subset of these parameters and a full reconstruction is not needed. A paradigmatic example is a scenario where one aims at determining all the reduced states only up to a given size. Overlapping tomography provides constructions to address this problem with a number of product measurements much smaller than what is obtained when performing independent tomography of each reduced state. There are however many relevant physical systems with a natural notion of locality where one is mostly interested in the reduced states of neighboring particles. In this work, we study this form of local overlapping tomography. First of all, we show that, contrary to its full version, the number of product-measurement settings needed for local overlapping tomography does not grow with system size. Then, we present strategies for qubit and fermionic systems in selected lattice geometries. The developed methods find a natural application in the estimation of many-body systems prepared in current quantum simulators or quantum computing devices, where interactions are often local.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Reconstructing the full quantum state of a many-body system requires the estimation of a number of parameters that grows exponentially with system size. Nevertheless, there are situations in which one is only interested in a subset of these parameters and a full reconstruction is not needed. A paradigmatic example is a scenario where one aims at determining all the reduced states only up to a given size. Overlapping tomography provides constructions to address this problem with a number of product measurements much smaller than what is obtained when performing independent tomography of each reduced state. There are however many relevant physical systems with a natural notion of locality where one is mostly interested in the reduced states of neighboring particles. In this work, we study this form of local overlapping tomography. First of all, we show that, contrary to its full version, the number of product-measurement settings needed for local overlapping tomography does not grow with system size. Then, we present strategies for qubit and fermionic systems in selected lattice geometries. The developed methods find a natural application in the estimation of many-body systems prepared in current quantum simulators or quantum computing devices, where interactions are often local.
202.
Shivan Mittal, Nicholas Hunter-Jones
Local random quantum circuits form approximate designs on arbitrary architectures Talk
2024.
@Talk{T24_309,
title = {Local random quantum circuits form approximate designs on arbitrary architectures},
author = {Shivan Mittal and Nicholas Hunter-Jones},
year = {2024},
date = {2024-01-01},
abstract = {We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We consider random quantum circuits (RQC) on arbitrary connected graphs whose edges determine the allowed 2-qudit interactions. Prior work has established that such $n$-qudit circuits with local dimension $q$ on 1D, complete, and $D$-dimensional graphs form approximate unitary designs, that is, they generate unitaries from distributions close to the Haar measure on the unitary group $U(q^n)$ after polynomially many gates. Here, we extend those results by proving that RQCs comprised of $O(poly(n,k))$ gates on a wide class of graphs form approximate unitary $k$-designs. We prove that RQCs on graphs with spanning trees of bounded degree and height form $k$-designs after $O(|E|n rm poly(k))$ gates, where $|E|$ is the number of edges in the graph. Furthermore, we identify larger classes of graphs for which RQCs generate approximate designs in polynomial circuit size. For $k łeq 4$, we show that RQCs on graphs of certain maximum degrees form designs after $O(|E|n)$ gates, providing explicit constants. We determine our circuit size bounds from the spectral gaps of local Hamiltonians. To that end, we extend the finite-size (or Knabe) method for bounding gaps of frustration-free Hamiltonians on regular graphs to arbitrary connected graphs. We further introduce a new method based on the Detectability Lemma for determining the spectral gaps of Hamiltonians on arbitrary graphs. Our methods have wider applicability as the first method provides a succinct alternative proof of [Commun. Math. Phys. 291, 257 (2009)] and the second method proves that RQCs on any connected architecture form approximate designs in quasi-polynomial circuit size.
203.
Chun-Yu Chen, Gelo Noel Tabia, Kai-Siang Chen, Yeong-Cherng Liang
Local randomness from quantum correlations on the no-signaling-boundary Poster
2023.
Abstract | Links:
@Poster{P7150,
title = {Local randomness from quantum correlations on the no-signaling-boundary},
author = {Chun-Yu Chen and Gelo Noel Tabia and Kai-Siang Chen and Yeong-Cherng Liang},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688093416-poster-Poster-Improved_finite_size_local_randomness_from_NSBQC_v3.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688093416-video-2023TQC_poster_presentation.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Device-independent randomness generation uses the violation of a Bell inequality to verify that the outputs of a nonlocal game are truly random. We focus on ``local'' randomness expansion protocols, where the extracted bits are random even to one of the involved parties. By incorporating zero-probability constraints into the Clauser-Horne-Shimony-Holt (CHSH) nonlocal game, we enhance the extractable rate in both asymptotic and finite-size regimes. Using the generalized entropy accumulation theorem and refining the second-order correction terms, we achieve a rate of up to 0.9 bit-per-round in our modified protocols, surpassing the standard CHSH game's maximum of 0.55 bits. Our results demonstrate some tolerance even without strictly enforcing the zero-probability constraints.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Device-independent randomness generation uses the violation of a Bell inequality to verify that the outputs of a nonlocal game are truly random. We focus on ``local'' randomness expansion protocols, where the extracted bits are random even to one of the involved parties. By incorporating zero-probability constraints into the Clauser-Horne-Shimony-Holt (CHSH) nonlocal game, we enhance the extractable rate in both asymptotic and finite-size regimes. Using the generalized entropy accumulation theorem and refining the second-order correction terms, we achieve a rate of up to 0.9 bit-per-round in our modified protocols, surpassing the standard CHSH game's maximum of 0.55 bits. Our results demonstrate some tolerance even without strictly enforcing the zero-probability constraints.
204.
Shin Ho Choe, Robert Koenig
Long-range data transmission in a fault-tolerant quantum bus architecture Poster
2023.
@Poster{P6760,
title = {Long-range data transmission in a fault-tolerant quantum bus architecture},
author = {Shin Ho Choe and Robert Koenig},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
205.
Touheed Anwar Atif, Mohammed Aamir Sohail, S. Sandeep Pradhan
Lossy Quantum Source Coding with a Global Error Criterion based on a Posterior Reference Map Poster
2023.
@Poster{P718,
title = {Lossy Quantum Source Coding with a Global Error Criterion based on a Posterior Reference Map},
author = {Touheed Anwar Atif and Mohammed Aamir Sohail and S. Sandeep Pradhan},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
206.
Áron Rozgonyi, Tamás Kiss, Orsolya Kálmán, Gábor Széchenyi, Zoltán Udvarnoki
Machine learning assisted tripartite entanglement distillation Poster
2023.
@Poster{P8297,
title = {Machine learning assisted tripartite entanglement distillation},
author = {Áron Rozgonyi and Tamás Kiss and Orsolya Kálmán and Gábor Széchenyi and Zoltán Udvarnoki},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
207.
Daniel Stilck França, Cambyse Rouze, Álvaro Alhambra
Making both ends meet: from efficient simulation to universal quantum computing with quantum Gibbs sampling Talk
2024.
@Talk{T24_359,
title = {Making both ends meet: from efficient simulation to universal quantum computing with quantum Gibbs sampling},
author = {Daniel Stilck França and Cambyse Rouze and Álvaro Alhambra},
year = {2024},
date = {2024-01-01},
abstract = {The preparation of thermal states of matter is a crucial task in quantum simulation. In this work, we prove that an efficiently implementable dissipative evolution recently introduced by Chen et al. thermalizes into its equilibrium Gibbs state in time scaling polynomially with system size at high enough temperatures for any Hamiltonian that satisfies a Lieb-Robinson bound, such as local Hamiltonians on a lattice. Furthermore, we show the efficient adiabatic preparation of the associated purifications or ``thermofield double" states. To the best of our knowledge, these are the first results rigorously establishing the efficient preparation of high temperature Gibbs states and their purifications. In the low-temperature regime, we show that implementing this family of Lindbladians for inverse temperatures logarithmic in the system's size is polynomially equivalent to standard quantum computation. On a technical level, for high temperatures, our proof makes use of the mapping of the generator of the evolution into a Hamiltonian and the analysis of the stability of its gap. For low temperature, we instead perform a perturbation at zero temperature of the Laplace transform of the energy observable at fixed runtime, and resort to circuit-to-Hamiltonian mappings akin to the proof of universality of quantum adiabatic computing. Taken together, our results show that the family of Lindbladians of Chen et al. efficiently prepares a large class of quantum many-body states of interest, and have the potential to mirror the success of classical Monte Carlo methods for quantum many-body systems.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
The preparation of thermal states of matter is a crucial task in quantum simulation. In this work, we prove that an efficiently implementable dissipative evolution recently introduced by Chen et al. thermalizes into its equilibrium Gibbs state in time scaling polynomially with system size at high enough temperatures for any Hamiltonian that satisfies a Lieb-Robinson bound, such as local Hamiltonians on a lattice. Furthermore, we show the efficient adiabatic preparation of the associated purifications or ``thermofield double" states. To the best of our knowledge, these are the first results rigorously establishing the efficient preparation of high temperature Gibbs states and their purifications. In the low-temperature regime, we show that implementing this family of Lindbladians for inverse temperatures logarithmic in the system's size is polynomially equivalent to standard quantum computation. On a technical level, for high temperatures, our proof makes use of the mapping of the generator of the evolution into a Hamiltonian and the analysis of the stability of its gap. For low temperature, we instead perform a perturbation at zero temperature of the Laplace transform of the energy observable at fixed runtime, and resort to circuit-to-Hamiltonian mappings akin to the proof of universality of quantum adiabatic computing. Taken together, our results show that the family of Lindbladians of Chen et al. efficiently prepares a large class of quantum many-body states of interest, and have the potential to mirror the success of classical Monte Carlo methods for quantum many-body systems.
208.
Andreas Klingler, Mirte Eyden, Sebastian Stengele, Tobias Reinhart, Gemma De Las Cuevas
Many bounded versions of undecidable problems are NP-hard Poster
2023.
Abstract | Links:
@Poster{P3656,
title = {Many bounded versions of undecidable problems are NP-hard},
author = {Andreas Klingler and Mirte Eyden and Sebastian Stengele and Tobias Reinhart and Gemma De Las Cuevas},
url = {https://arxiv.org/abs/2211.13532 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688048245-poster-3656.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688048245-video-3656.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.
209.
Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture Poster
2023.
@Poster{P8247,
title = {Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture},
author = {Andris Ambainis and Harry Buhrman and Koen Leijnse and Subhasree Patro and Florian Speelman},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
210.
Rahul Jain, Georgios Piliouras, Ryann Sim
Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence Poster
2023.
@Poster{P7043,
title = {Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence},
author = {Rahul Jain and Georgios Piliouras and Ryann Sim},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
211.
John Martin, Eduardo Serrano-Ensástiga
Maximum entanglement of mixed symmetric states under unitary transformations Poster
2023.
@Poster{P2449,
title = {Maximum entanglement of mixed symmetric states under unitary transformations},
author = {John Martin and Eduardo Serrano-Ensástiga},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688712541-poster-poster_SAS.pdf},
year = {2023},
date = {2023-01-01},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
212.
Faedi Loulidi, Ion Nechita
Measurement incompatibility vs. Bell non-locality: an approach via tensor norms Poster
2023.
@Poster{P1835,
title = {Measurement incompatibility vs. Bell non-locality: an approach via tensor norms},
author = {Faedi Loulidi and Ion Nechita},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
213.
Cihan Okay, Ho Yiu Chung, Selman Ipek
Mermin polytopes in quantum computation and foundations Poster
2023.
@Poster{P9989,
title = {Mermin polytopes in quantum computation and foundations},
author = {Cihan Okay and Ho Yiu Chung and Selman Ipek},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
214.
Palash Pandya, Marcin Wieśniak
Minimum Hilbert-Schmidt Distance and Optimal Entanglement Witnesses Poster
2023.
@Poster{P9076,
title = {Minimum Hilbert-Schmidt Distance and Optimal Entanglement Witnesses},
author = {Palash Pandya and Marcin Wieśniak},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
215.
Jan Ole Ernst, Felix Tennie
Mode entanglement in fermionic and bosonic Harmonium Poster
2023.
@Poster{P4687,
title = {Mode entanglement in fermionic and bosonic Harmonium},
author = {Jan Ole Ernst and Felix Tennie},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
216.
Margarida Pereira, Guillermo Currás-Lorenzo, Álvaro Navarrete, Akihiro Mizutani, Go Kato, Marcos Curty, Kiyoshi Tamaki
Modified BB84 quantum key distribution protocol robust to source imperfections Poster
2023.
@Poster{P3522,
title = {Modified BB84 quantum key distribution protocol robust to source imperfections},
author = {Margarida Pereira and Guillermo Currás-Lorenzo and Álvaro Navarrete and Akihiro Mizutani and Go Kato and Marcos Curty and Kiyoshi Tamaki},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
217.
Junaid Aftab, Dong An, Konstantina Trivisa
Multi-product Hamiltonian simulation with explicit commutator scaling Talk
2024.
@Talk{T24_381,
title = {Multi-product Hamiltonian simulation with explicit commutator scaling},
author = {Junaid Aftab and Dong An and Konstantina Trivisa},
year = {2024},
date = {2024-01-01},
abstract = {The multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders the practical advantage of MPF ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
The multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders the practical advantage of MPF ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.
218.
Siyuan Niu, Aida Todri-Sanial
Multi-programming Benchmarking for Quantum Computing on Trapped-Ion and Superconducting Devices Poster
2023.
@Poster{P2687,
title = {Multi-programming Benchmarking for Quantum Computing on Trapped-Ion and Superconducting Devices},
author = {Siyuan Niu and Aida Todri-Sanial},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
219.
Allyson Silva, Xiangyi Zhang, Zachary Webb, Mia Kramer, Chan Woo Yang, Xiao Liu, Jessica Lemieux, Kawai Chen, Artur Scherer, Pooya Ronagh
Multi-qubit Lattice Surgery Scheduling Talk
2024.
@Talk{T24_426,
title = {Multi-qubit Lattice Surgery Scheduling},
author = {Allyson Silva and Xiangyi Zhang and Zachary Webb and Mia Kramer and Chan Woo Yang and Xiao Liu and Jessica Lemieux and Kawai Chen and Artur Scherer and Pooya Ronagh},
year = {2024},
date = {2024-01-01},
abstract = {Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We first show that, using the tableau representation of Clifford gates, this transpilation can be run in linear time with respect to the circuit length, and observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and real-world circuits demonstrates the method's scalability and performance. We show that the transpilation reduces the circuit length by 82% on average, and that the resulting circuit of multi-qubit gates has an average reduction of 20.5% in the expected circuit execution time compared to serial execution.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Fault-tolerant quantum computation using two-dimensional topological quantum error correcting codes can benefit from multi-qubit long-range operations. By using simple commutation rules, a quantum circuit can be transpiled into a sequence of solely non-Clifford multi-qubit gates. Prior work on fault-tolerant compilation avoids optimal scheduling of such gates since they reduce the parallelizability of the circuit. We first show that, using the tableau representation of Clifford gates, this transpilation can be run in linear time with respect to the circuit length, and observe that the reduced parallelization potential is outweighed by the significant reduction in the number of gates. We therefore devise a method for scheduling multi-qubit lattice surgery using an earliest-available-first policy, solving the associated forest packing problem using a representation of the multi-qubit gates as Steiner trees. Our extensive testing on random and real-world circuits demonstrates the method's scalability and performance. We show that the transpilation reduces the circuit length by 82% on average, and that the resulting circuit of multi-qubit gates has an average reduction of 20.5% in the expected circuit execution time compared to serial execution.
220.
Stefano Chessa, Vittorio Giovannetti
Multilevel amplitude damping channels: models, capacities, perspectives Poster
2023.
@Poster{P4288,
title = {Multilevel amplitude damping channels: models, capacities, perspectives},
author = {Stefano Chessa and Vittorio Giovannetti},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
221.
Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
Multipartite to tripartite reductions for LU and SLOCC equivalences Talk
2024.
@Talk{T24_23,
title = {Multipartite to tripartite reductions for LU and SLOCC equivalences},
author = {Zhili Chen and Joshua A. Grochow and Youming Qiao and Gang Tang and Chuanqi Zhang},
year = {2024},
date = {2024-01-01},
abstract = {We show that classifying LU and SLOCC equivalences of d-partite pure states can be reduced to classifying such equivalences for tripartite pure states. To this end, we employ techniques from various areas, including path algebras from representation theory of associative algebras, and gadget constructions from computational complexity theory.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We show that classifying LU and SLOCC equivalences of d-partite pure states can be reduced to classifying such equivalences for tripartite pure states. To this end, we employ techniques from various areas, including path algebras from representation theory of associative algebras, and gadget constructions from computational complexity theory.
222.
Yihui Quek, Eneet Kaur, Mark Wilde
Multivariate trace estimation in constant quantum depth Poster
2023.
@Poster{P8218,
title = {Multivariate trace estimation in constant quantum depth},
author = {Yihui Quek and Eneet Kaur and Mark Wilde},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
223.
Kai Lin Ong
Near-idempotents of quaternary group algebras and their applications in designing quantum code Poster
2023.
Abstract | Links:
@Poster{P5738,
title = {Near-idempotents of quaternary group algebras and their applications in designing quantum code},
author = {Kai Lin Ong},
url = {https://link.springer.com/article/10.1007/s11128-023-03904-7 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688280711-poster-5738.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688280711-video-5738.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Define near-idempotents of a group algebra $mathbbF_qG$ as its elements $fınmathbbF_qG$ such that $f^n=e$ for some idempotent $e$ and $nınmathbbZ^+$. The smallest such $n$ is termed the degree of $f$. Near-idempotents can be viewed as a generalisation of idempotents, as the latter is just near-idempotents of degree 1. While theories of near-idempotents were well-established in ring theory, general frameworks of constructing codes using near-idempotents remain rather unexplored. Therefore, this session is devoted to exploring classes of quantum stabilizer codes and their properties, which near-idempotents are served as the generator of their underlying additive codes over $mathbbF_4$. This is primarily done by adopting a perspective of viewing codes over $mathbbF_4$ isomorphically as group algebras over the same finite field. Via the lens of group algebras, we characterize conditions on near-idempotents that enables their additive codes to sufficiently satisfies the inner product criterion for stabilizer formalism, then characterizes the constructed codes and some of their properties. Our results shows that a number of quantum codes generated by near-idempotents coincide with the best known parameters.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
Define near-idempotents of a group algebra $mathbbF_qG$ as its elements $fınmathbbF_qG$ such that $f^n=e$ for some idempotent $e$ and $nınmathbbZ^+$. The smallest such $n$ is termed the degree of $f$. Near-idempotents can be viewed as a generalisation of idempotents, as the latter is just near-idempotents of degree 1. While theories of near-idempotents were well-established in ring theory, general frameworks of constructing codes using near-idempotents remain rather unexplored. Therefore, this session is devoted to exploring classes of quantum stabilizer codes and their properties, which near-idempotents are served as the generator of their underlying additive codes over $mathbbF_4$. This is primarily done by adopting a perspective of viewing codes over $mathbbF_4$ isomorphically as group algebras over the same finite field. Via the lens of group algebras, we characterize conditions on near-idempotents that enables their additive codes to sufficiently satisfies the inner product criterion for stabilizer formalism, then characterizes the constructed codes and some of their properties. Our results shows that a number of quantum codes generated by near-idempotents coincide with the best known parameters.
224.
Zongbo Bao, Penghui Yao
Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels Poster
2023.
@Poster{P2705,
title = {Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels},
author = {Zongbo Bao and Penghui Yao},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
225.
Roberto Rubboli, Marco Tomamichel
New additivity properties of the relative entropy of entanglement and its generalizations Workshop
2023.
Abstract | Links:
@Workshop{T7681,
title = {New additivity properties of the relative entropy of entanglement and its generalizations},
author = {Roberto Rubboli and Marco Tomamichel},
url = {https://arxiv.org/abs/2211.12804},
year = {2023},
date = {2023-01-01},
abstract = {We prove that the relative entropy of entanglement is additive when at least one of the two states belongs to some specific class. We show that these classes include bipartite pure, maximally correlated, GHZ, Bell diagonal, isotropic, and generalized Dicke states. Previously, additivity was established only if both states belong to the same class. Moreover, we extend these results to entanglement monotones based on the α-$z$ Rényi relative entropy. Notably, this family of monotones includes also the generalized robustness of entanglement and the geometric measure of entanglement. In addition, we prove that any monotone based on a quantum relative entropy is not additive for general states.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
We prove that the relative entropy of entanglement is additive when at least one of the two states belongs to some specific class. We show that these classes include bipartite pure, maximally correlated, GHZ, Bell diagonal, isotropic, and generalized Dicke states. Previously, additivity was established only if both states belong to the same class. Moreover, we extend these results to entanglement monotones based on the α-$z$ Rényi relative entropy. Notably, this family of monotones includes also the generalized robustness of entanglement and the geometric measure of entanglement. In addition, we prove that any monotone based on a quantum relative entropy is not additive for general states.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.
226.
Eric Culf, Arthur Mehta
New Approaches to Complexity via Quantum Graphs Talk
2024.
@Talk{T24_123,
title = {New Approaches to Complexity via Quantum Graphs},
author = {Eric Culf and Arthur Mehta},
year = {2024},
date = {2024-01-01},
abstract = {Problems based on the structure of graphs — for example finding cliques, independent sets, or colourings — are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalisation of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We show that when quantifying over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2)-complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantifying over a subset of entanglement-breaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously-studied complete problem. We also give a new proof of the celebrated reduction of QMA(k) to QMA(2). In parallel, we study a version of the closely-related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Problems based on the structure of graphs — for example finding cliques, independent sets, or colourings — are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalisation of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We show that when quantifying over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2)-complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantifying over a subset of entanglement-breaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously-studied complete problem. We also give a new proof of the celebrated reduction of QMA(k) to QMA(2). In parallel, we study a version of the closely-related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.
227.
Xavier Coiteux-Roy, Francesco D'Amore, Rishikesh Gajjala, Fabian Kuhn, Francois Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela
No distributed quantum advantage for approximate graph coloring Talk
2024.
@Talk{T24_60,
title = {No distributed quantum advantage for approximate graph coloring},
author = {Xavier Coiteux-Roy and Francesco D'Amore and Rishikesh Gajjala and Fabian Kuhn and Francois Le Gall and Henrik Lievonen and Augusto Modanese and Marc-Olivier Renou and Gustav Schmid and Jukka Suomela},
year = {2024},
date = {2024-01-01},
abstract = {We give an almost complete characterization of the hardness of $c$-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a $c$-coloring in χ-chromatic graphs in $tildemathcalO(n^frac1alpha)$ rounds, with $alpha = biglłfloorfracc-1chi - 1bigrrfloor$. ıtem We prove that any distributed algorithm for this problem requires $Ømega(n^frac1alpha)$ rounds. endenumerate Our upper bound holds in the classical, deterministic $mathsfLOCAL$ model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic $mathsfLOCAL$ and randomized $mathsfLOCAL$ but also $mathsfquantum$-$mathsfLOCAL$, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We give an almost complete characterization of the hardness of $c$-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a $c$-coloring in χ-chromatic graphs in $tildemathcalO(n^frac1alpha)$ rounds, with $alpha = biglłfloorfracc-1chi - 1bigrrfloor$. ıtem We prove that any distributed algorithm for this problem requires $Ømega(n^frac1alpha)$ rounds. endenumerate Our upper bound holds in the classical, deterministic $mathsfLOCAL$ model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic $mathsfLOCAL$ and randomized $mathsfLOCAL$ but also $mathsfquantum$-$mathsfLOCAL$, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.
228.
Swapnil Bhowmick, Abhay Srivastav, Arun Kumar Pati
No-Masking Theorem for Observables and No-Bit Commitment Poster
2023.
@Poster{P7859,
title = {No-Masking Theorem for Observables and No-Bit Commitment},
author = {Swapnil Bhowmick and Abhay Srivastav and Arun Kumar Pati},
year = {2023},
date = {2023-01-01},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
229.
Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck Franca, Yihui Quek
Noise-induced shallow circuits and absence of barren plateaus Talk
2024.
@Talk{T24_409,
title = {Noise-induced shallow circuits and absence of barren plateaus},
author = {Antonio Anna Mele and Armando Angrisani and Soumik Ghosh and Sumeet Khatri and Jens Eisert and Daniel Stilck Franca and Yihui Quek},
year = {2024},
date = {2024-01-01},
abstract = {We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
We study the impact of non-unital noise on random quantum circuits, generalizing many previous results about the impact of noise on near-term computation that assumed that noise was unital or even specifically depolarizing. Non-unital noise (a class that includes amplitude damping noise and other loss processes) is a more natural noise model for certain physical platforms than unital noise. Yet it is analytically more challenging and has in the past led to starkly different conclusions about computational tasks, like error correction and random circuit sampling. Our main result is that non-unital noise ``truncates" deep random quantum circuits to effectively have logarithmic depth, in the task of computing Pauli expectation values. By way of proving this, we contribute a contraction result for quantum circuits under non-unital noise, which significantly strengthens all previous results in this setting. As an application, we show that circuits used for variational quantum algorithms, under non-unital noise, avoid the problem of barren plateaus for cost functions made of local observables. This is not necessarily good news, however, as their effective shallowness also makes such circuits vulnerable to classical simulators. Accordingly, we also provide an algorithm to estimate local expectation values in the presence of non-unital noise, that succeeds with high probability over the ensemble. The runtime of our algorithm is independent of both the number of qubits and circuit depth, and depends polynomially on the accuracy for one-dimensional architectures and quasi-polynomially for two-dimensional ones. While the hardness of sampling from random circuits under non–unital noise is yet unresolved, our results indicate that for the vast majority of quantum circuits under non-unital noise, we are unlikely to glean quantum advantage for algorithms that output expectation values.
230.
Marco Fellous Asiani, Moein Naseri, Alexander Streltsov, Michał Oszmaniec
Noise-resilient quantum circuits for qubits admitting a noise bias Poster
2023.
@Poster{P214,
title = {Noise-resilient quantum circuits for qubits admitting a noise bias},
author = {Marco Fellous Asiani and Moein Naseri and Alexander Streltsov and Michał Oszmaniec},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
231.
Sarah Hagen, Eric Chitambar
Non-Classical Zero Communication Reductions Poster
2023.
@Poster{P8908,
title = {Non-Classical Zero Communication Reductions},
author = {Sarah Hagen and Eric Chitambar},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688135349-poster-8908.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688135349-video-8908.mp4},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
232.
Chandan Mahto, Vijay Pathak, Ardra K. S, Anil Shaji
Nonclassical correlations in subsystems of globally entangled quantum states Poster
2023.
@Poster{P3586,
title = {Nonclassical correlations in subsystems of globally entangled quantum states},
author = {Chandan Mahto and Vijay Pathak and Ardra K. S and Anil Shaji},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
233.
Sayantan Chakraborty, Upendra Kapshikar
Novel chain rules for one-shot entropic quantities via operational methods Poster
2023.
@Poster{P2552,
title = {Novel chain rules for one-shot entropic quantities via operational methods},
author = {Sayantan Chakraborty and Upendra Kapshikar},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
234.
Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
On linear-algebraic notions of expansion Poster
2023.
Abstract | Links:
@Poster{P2299,
title = {On linear-algebraic notions of expansion},
author = {Yinan Li and Youming Qiao and Avi Wigderson and Yuval Wigderson and Chuanqi Zhang},
url = {https://arxiv.org/pdf/2212.13154.pdf https://arxiv.org/pdf/2206.04815.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1685063955-poster-2299.pdf},
year = {2023},
date = {2023-01-01},
abstract = {A fundamental fact about bounded-degree graph expanders is that three notions of expansion—vertex expansion, edge expansion, and spectral expansion—are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion. There are two well-studied notions of linear-algebraic expansion, namely dimension expansion [1] (defined in analogy to graph vertex expansion) and quantum expansion [2, 3] (defined in analogy to graph spectral expansion). Lubotzky and Zelmanov [4] proved that the latter implies the former. We prove that the converse is false: there are dimension expanders which are not quantum expanders. Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of graph edge expansion. The first of these is quantum edge expansion, which was introduced by Hastings [5], and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky-Zelmanov result [4] that quantum expanders are dimension expanders.
[1] Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson. Definition and existence of dimension expanders. Discussion (no written record), 2004.
[2] Avraham Ben-Aroya and Amnon Ta-Shma. Quantum expanders and the quantum entropy difference problem. ArXiv:quant-ph/0702129, 2007.
[3] M. B. Hastings. Entropy and entanglement in quantum ground states. Phys. Rev. B, 76:035114, Jul 2007.
[4] Alexander Lubotzky and Efim Zelmanov. Dimension expanders. Journal of Algebra, 319(2):730–738, 2008. [5] M. B. Hastings. Random unitaries give quantum expanders. Physical Review A, 76:032315, Sep 2007.},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
A fundamental fact about bounded-degree graph expanders is that three notions of expansion—vertex expansion, edge expansion, and spectral expansion—are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion. There are two well-studied notions of linear-algebraic expansion, namely dimension expansion [1] (defined in analogy to graph vertex expansion) and quantum expansion [2, 3] (defined in analogy to graph spectral expansion). Lubotzky and Zelmanov [4] proved that the latter implies the former. We prove that the converse is false: there are dimension expanders which are not quantum expanders. Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of graph edge expansion. The first of these is quantum edge expansion, which was introduced by Hastings [5], and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky-Zelmanov result [4] that quantum expanders are dimension expanders.
[1] Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson. Definition and existence of dimension expanders. Discussion (no written record), 2004.
[2] Avraham Ben-Aroya and Amnon Ta-Shma. Quantum expanders and the quantum entropy difference problem. ArXiv:quant-ph/0702129, 2007.
[3] M. B. Hastings. Entropy and entanglement in quantum ground states. Phys. Rev. B, 76:035114, Jul 2007.
[4] Alexander Lubotzky and Efim Zelmanov. Dimension expanders. Journal of Algebra, 319(2):730–738, 2008. [5] M. B. Hastings. Random unitaries give quantum expanders. Physical Review A, 76:032315, Sep 2007.
[1] Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson. Definition and existence of dimension expanders. Discussion (no written record), 2004.
[2] Avraham Ben-Aroya and Amnon Ta-Shma. Quantum expanders and the quantum entropy difference problem. ArXiv:quant-ph/0702129, 2007.
[3] M. B. Hastings. Entropy and entanglement in quantum ground states. Phys. Rev. B, 76:035114, Jul 2007.
[4] Alexander Lubotzky and Efim Zelmanov. Dimension expanders. Journal of Algebra, 319(2):730–738, 2008. [5] M. B. Hastings. Random unitaries give quantum expanders. Physical Review A, 76:032315, Sep 2007.
235.
Nico Piatkowski, Christa Zoufal
On Quantum Circuits for Discrete Graphical Models Poster
2023.
@Poster{P1902,
title = {On Quantum Circuits for Discrete Graphical Models},
author = {Nico Piatkowski and Christa Zoufal},
year = {2023},
date = {2023-01-01},
howpublished = {Poster},
keywords = {},
pubstate = {published},
tppubtype = {Poster}
}
236.
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner
On the complexity of hybrid quantum computation Workshop
2023.
Abstract | Links:
@Workshop{T9686,
title = {On the complexity of hybrid quantum computation},
author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner},
url = {https://arxiv.org/abs/2210.06454 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688218994-poster-9686.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688218994-video-9686.mp4},
year = {2023},
date = {2023-01-01},
abstract = {We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle:
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle:
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.
237.
Eric Chitambar, Felix Leditzky
On the Duality of Teleportation and Dense Coding Workshop
2023.
@Workshop{T2414,
title = {On the Duality of Teleportation and Dense Coding},
author = {Eric Chitambar and Felix Leditzky},
year = {2023},
date = {2023-01-01},
abstract = {Quantum teleportation is a quantum communication primitive that allows a long-distance quantum channel to be built using pre-shared entanglement and one-way classical communication. However, the quality of the established channel crucially depends on the quality of the pre-shared entanglement. In this work, we revisit the problem of using noisy entanglement for the task of teleportation. We first show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. This also yields a new proof of the known fact that bound entangled states cannot exceed the classical teleportation threshold. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. We also discuss the duality from a communication capacity point of view, deriving upper and lower bounds on the accessible information of a dense coding protocol in terms of the fidelity of its associated teleportation protocol. A corollary of this discussion is a simple proof of the previously established fact that bound entangled states do not provide any advantage in dense coding.},
howpublished = {Talk},
keywords = {},
pubstate = {published},
tppubtype = {Workshop}
}
Quantum teleportation is a quantum communication primitive that allows a long-distance quantum channel to be built using pre-shared entanglement and one-way classical communication. However, the quality of the established channel crucially depends on the quality of the pre-shared entanglement. In this work, we revisit the problem of using noisy entanglement for the task of teleportation. We first show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. This also yields a new proof of the known fact that bound entangled states cannot exceed the classical teleportation threshold. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. We also discuss the duality from a communication capacity point of view, deriving upper and lower bounds on the accessible information of a dense coding protocol in terms of the fidelity of its associated teleportation protocol. A corollary of this discussion is a simple proof of the previously established fact that bound entangled states do not provide any advantage in dense coding.
238.
Marcel Dall'Agnol, Nicholas Spooner
On the Necessity of Collapsing for Post-Quantum and Quantum Commitments Conference
2023.
Abstract | Links:
@Conference{T2208,
title = {On the Necessity of Collapsing for Post-Quantum and Quantum Commitments},
author = {Marcel Dall'Agnol and Nicholas Spooner},
url = {https://eprint.iacr.org/2022/786 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688327217-video-Talk.mp4},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Collapse binding and collapsing were proposed as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the ""lifting"" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).},
howpublished = {Talk and Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {Conference}
}
Collapse binding and collapsing were proposed as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the ""lifting"" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).
239.
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
On the power of nonstandard quantum oracles Conference
2023.
Abstract | Links:
@Conference{T7817,
title = {On the power of nonstandard quantum oracles},
author = {Roozbeh Bassirian and Bill Fefferman and Kunal Marwaha},
url = {https://arxiv.org/abs/2212.00098},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.},
howpublished = {Talk and Proceedings},
keywords = {},
pubstate = {published},
tppubtype = {Conference}
}
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.
240.
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
On the Power of Quantum Distributed Proofs Talk
2024.
@Talk{T24_132,
title = {On the Power of Quantum Distributed Proofs},
author = {Atsuya Hasegawa and Srijita Kundu and Harumichi Nishimura},
year = {2024},
date = {2024-01-01},
abstract = {Quantum nondeterministic distributed computing was recently introduced as $mathsfdQMA$ (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In $mathsfdQMA$ protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al.~showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical or not. In this paper, we further investigate and characterize the power of the $mathsfdQMA$ protocols for various decision problems. First, we give a more efficient $mathsfdQMA$ protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient $mathsfdQMA$ protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication complexity protocols. Third, in a line network, we construct an efficient $mathsfdQMA$ protocol for a problem that has an efficient two-party $mathsfQMA$ communication complexity protocol. Finally, we obtain the first lower bounds on the proof and communication cost of $mathsfdQMA$ protocols. To prove a lower bound on the equality problem, we show any $mathsfdQMA$ protocol with an entangled proof between nodes can be simulated with a $mathsfdQMA$ protocol with a separable proof between nodes by using a $mathsfQMA$ communication-complete problem introduced by Raz and Shpilka (CCC 2004).},
keywords = {},
pubstate = {published},
tppubtype = {Talk}
}
Quantum nondeterministic distributed computing was recently introduced as $mathsfdQMA$ (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In $mathsfdQMA$ protocols, with the help of quantum proofs and local communication, nodes on a network verify some global property of the network. Fraigniaud et al.~showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical or not. In this paper, we further investigate and characterize the power of the $mathsfdQMA$ protocols for various decision problems. First, we give a more efficient $mathsfdQMA$ protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient $mathsfdQMA$ protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication complexity protocols. Third, in a line network, we construct an efficient $mathsfdQMA$ protocol for a problem that has an efficient two-party $mathsfQMA$ communication complexity protocol. Finally, we obtain the first lower bounds on the proof and communication cost of $mathsfdQMA$ protocols. To prove a lower bound on the equality problem, we show any $mathsfdQMA$ protocol with an entangled proof between nodes can be simulated with a $mathsfdQMA$ protocol with a separable proof between nodes by using a $mathsfQMA$ communication-complete problem introduced by Raz and Shpilka (CCC 2004).
