TQC 2024

@Poster{P24_379,

title = {Arbitrary Polynomial Separations in Trainable Quantum Machine Learning},

author = {Eric Anschuetz and Xun Gao},

url = {https://arxiv.org/abs/2402.08606},

year  = {2024},

date = {2024-01-01},

abstract = {Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks in performing a classical sequence modeling task. Furthermore, each unit cell of the introduced class of QNNs is computationally efficient, implementable in constant time on a quantum device. The classical networks we prove a separation over include well-known examples such as recurrent neural networks and Transformers. We show that quantum contextuality is the source of the expressivity separation, suggesting that other classical sequence learning problems with long-time correlations may be a regime where practical advantages in quantum machine learning may exist.},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_135,

title = {Clustering theorem in 1D long-range interacting systems at arbitrary temperatures},

author = {Yusuke Kimura and Tomotaka Kuwahara},

url = {https://arxiv.org/abs/2403.11431},

year  = {2024},

date = {2024-01-01},

abstract = {This paper delves into a fundamental aspect of quantum statistical mechanics – the absence of thermal phase transitions in one-dimensional (1D) systems. Originating from Ising's analysis of the 1D spin chain, this concept has been pivotal in understanding 1D quantum phases, especially those with finite-range interactions as extended by Araki. In this work, we focus on quantum long-range interactions and successfully derive a clustering theorem applicable to a wide range of interaction decays at arbitrary temperatures. This theorem applies to any interaction forms that decay faster than r^-2 and does not rely on translation invariance or infinite system size assumptions. Also, we rigorously established that the temperature dependence of the correlation length is given by e^const.β, which is the same as the classical cases. Our findings indicate the absence of phase transitions in 1D systems with super-polynomially decaying interactions, thereby expanding upon previous theoretical research. To overcome significant technical challenges originating from the divergence of the imaginary-time Lieb-Robinson bound, we utilize the quantum belief propagation to refine the cluster expansion method. This approach allowed us to address divergence issues effectively and contributed to a deeper understanding of low-temperature behaviors in 1D quantum systems.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_242,

title = {Entanglement sharing across a damping-dephasing channel},

author = {Vikesh Siddhu and Dina Abdelhadi and Tomas Jochym-O'Connor and John Smolin},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_226,

title = {Fast quantum interconnects via constant-rate entanglement distillation},

author = {Christopher Pattison and Gefen Baranes and Juan Pablo Bonilla Ataides and Mikhail Lukin and Hengyun Zhou},

year  = {2024},

date = {2024-01-01},

abstract = {Distributed quantum computing allows the modular construction of large-scale quantum computers and enables new protocols for verifiably-secure quantum computation. However, such applications place stringent demands on the fidelity and rate of remote logical entanglement generation, which are not met by existing methods for quantum interconnects. In this work, we develop constant-rate entanglement distillation methods to address this bottleneck. By using a sequence of two-way entanglement distillation protocols with increasing rate, we achieve constant-rate entanglement distillation with competitive overhead. We encode the distributed Bell pairs into error-correcting codes prior to distillation, thereby making most efficient use of the noisy, distributed entanglement while only incurring a modest increase in memory footprint. We prove that our protocol achieves a constant expected ratio of physical to logical Bell pairs, for a given input error rate, and perform extensive numerical optimization to identify concrete code sequences with low overhead. We further analyze the possible improvements afforded by our scheme in the execution of concrete distributed algorithms. We find that our scheme outperforms existing quantum interconnect schemes by an order of magnitude, paving the way towards fast, distributed quantum computing.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_109,

title = {Information causality as a tool for bounding the set of quantum correlations},

author = {Mariami Gachechiladze and Prabhav Jain and Nikolai Miklin},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_85,

title = {Nonlocality under computational assumptions},

author = {Khashayar Barooti and Alexandru Gheorghiu and Grzegorz Głuch and Marc-Olivier Renou},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_363,

title = {On the computational complexity of equilibrating quantum systems},

author = {Lennart Bittel and Sevag Gharibian and Martin Kliesch},

year  = {2024},

date = {2024-01-01},

abstract = {Understanding equilibration behavior of closed systems is an important but difficult problem. 

Intuitively, after some equilibration time, many-body systems typically transition to a steady state, in which expectation values become stationary. 

Sometimes, after long evolution times, however, a system can exit an equilibrium state again. 

Thus, it is natural to ask (i) for how long is an expectation value of a time-evolved observable <O(t)> equilibrated and (ii) what are the extremal values of <O(t)>. For simple observables and states under k-local Hamiltonian dynamics we show that the associated computational problems are (i) coNEXP-complete and (ii) NEXP-complete to answer for time scales given in scientific notation. 

Thus, no classical polynomial-time algorithm exist for these problems (unconditionally). Hence, understanding equilibration behavior of closed systems can be computationally intractable. 

We then show a similar result for estimating the ansatz error for a VQA setup, in which one can potentially reuse gate generators an arbitary number of times. 

Hence, we provide arguably rare examples of physically motivated NEXP-complete problems. Finally, we also derive upper bounds for the question of equilibration over all time. Here we show that the computational problem is contained in a subclass of EXPSPACE i.e. solvable in exponential space, but potentially double-exponential time.},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_331,

title = {Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms},

author = {Marc Wanner and Laura Lewis and Chiranjib Bhattacharyya and Devdatt Dubhashi and Alexandru Gheorghiu},

url = {https://arxiv.org/abs/2405.18489},

year  = {2024},

date = {2024-01-01},

abstract = {A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. A number of recent works gave provably efficient machine learning (ML) algorithms for learning ground states. Specifically, [1], introduced an approach for learning properties of the ground state of an n-qubit gapped local Hamiltonian H from data points sampled from Hamiltonians in the same phase of matter polynomial in n. This was subsequently improved by [2], to logarithmic number of samples with respect to system size when the geometry of the n-qubit system is known. In this work, we introduce two approaches that achieve a constant sample complexity, independent of system size, for learning ground state properties. Our first algorithm consists of a simple modification of the ML model used by Lewis et al. and applies to a property of interest known beforehand. Our second algorithm, which applies even if a description of the property is not known, is a deep neural network model. While empirical results showing the performance of neural networks have been demonstrated, to our knowledge, this is the first rigorous sample complexity bound on a neural network model for predicting ground state properties. We also perform numerical experiments that confirm the improved scaling of our approach compared to earlier results. 

References: Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6613):eabk3333, 2022. [2] Laura Lewis, Hsin-Yuan Huang, Viet T Tran, Sebastian Lehner, Richard Kueng, and John Preskill. Improved machine learning algorithm for predicting ground state properties. Nature Communications, 15(1):895, 2024.},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_387,

title = {Quantum algorithms for many-body spectroscopy using dynamics and classical shadows},

author = {Nishad Maskara and Stefan Ostermann and James Shee and Marcin Kalinowski and Abigail McClain Gomez and Rodrigo Araiza Bravo and Varun Menon and Christian Kokail and Hsin-Yuan Huang and Derek Wang and Anna Krylov and Norman Yao and Martin Head-Gordon and Mikhail Lukin and Susanne Yelin},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_190,

title = {Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations},

author = {Joseph Carolan and Alexander Poremba},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_140,

title = {Quantum Polynomial Hierarchies: Collapses, Karp-Lipton, and More},

author = {Avantika Agarwal and Sevag Gharibian and Sabee Grewal and Venkata Koppula and Dorian Rudolph and Justin Yirka},

url = {https://arxiv.org/abs/2401.01453 https://arxiv.org/abs/2401.01633},

year  = {2024},

date = {2024-01-01},

abstract = {The polynomial hierarchy (PH) has played a central role in complexity theory for the last 50 years. Given its significance, it is only natural to explore quantum generalizations, yet such generalizations remain embarrassingly not understood. 

This work studies several quantum generalizations of the quantifier-based definition of PH. The setup for these hierarchies is the same as for PH, except the verifier can perform quantum computations and the provers send different types of proofs (e.g., entangled quantum states, unentangled pure states). So, for example, QCPH is just like PH, except the verifier can perform quantum computation. 

We establish the following results: 

- (A collapse theorem for QCPH.) For any k ≥ 1, if the k-th levels of QCPH are equal, then QCPH collapses to its k-th level. 

- (Quantum-classical Karp-Lipton theorem.) If QCMA ⊆ BQP/mpoly, then QCPH collapses to its second level. That is, QCMA does not have poly-size quantum circuits unless QCPH collapses. 

- (QEPH collapses.) We introduce the entangled quantum polynomial hierarchy QEPH. We prove that QEPH collapses to its second level and equals QRG(1), the class of problems having one-turn quantum-refereed games. 

- (Error reduction for pureQPH and QEPH). We prove one-sided error reduction for pureQPH, which uses a new asymmetric version of the Harrow-Montanaro Product Test. We also show that error reduction is possible for QEPH. 

- (Relationship between hierarchies.) We prove that PH ⊆ QCPH ⊆ QPH ⊆ pureQPH ⊆ EXP^PP, and QEPH ⊆ QPH. Previously, it was not known if even PH ⊆ QPH, and the best upper bound on QPH was the exponential time hierarchy. - (Distribution hierarchies.) We introduce generalizations of PH and QCPH, where the provers send distributions over strings (instead of strings), we denote these by DistributionPH and DistributionQCPH. We prove that DistributionPH = PH and DistributionQCPH = QCPH by generalizing a game-theoretic result of Lipton and Young (1994).},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_40,

title = {Quantum Unpredictability},

author = {Tomoyuki Morimae and Shogo Yamada and Takashi Yamakawa},

url = {https://arxiv.org/abs/2405.04072},

year  = {2024},

date = {2024-01-01},

abstract = {Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a quantum analog of UPFs, which we call unpredictable state generators (UPSGs). UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs), and therefore UPSGs could exist even if one-way functions do not exist,similar to other recently introduced primitives like pseudorandom state generators (PRSGs), one-way state generators (OWSGs), and EFIs. In classical cryptography, UPFs are equivalent to PRFs, but in the quantum case, the equivalence is not clear, and UPSGs could be weaker than PRFSs. Despite this, we demonstrate that all known applications of PRFSs are also achievable with UPSGs. They include IND-CPA-secure secret-key encryption and EUFCMA-secure MACs with unclonable tags. Our findings suggest that, for many applications, quantum unpredictability, rather than quantum pseudorandomness, is sufficient.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_77,

title = {Shaded lightcones for classically accelerated quantum error mitigation},

author = {Andrew Eddins and Minh Tran and Patrick Rall},

url = {http://patrickrall.com/#not_available_online},

year  = {2024},

date = {2024-01-01},

abstract = {Abstract Noisy quantum computers introduce bias to the measured expectation values. Quantum error mitigation recovers the correct values by generally trading off the bias for an increase in the statistical variance of the measurement. Among error mitigation approaches, Probabilistic Error Cancellation (PEC) stands out as a method capable of eliminating all potential bias due to gate errors, in exchange for an exponentially large variance of the estimator. This variance can be significantly reduced by not mitigating errors lying outside the causal lightcone of the desired observable. The causal lightcone, however, can grossly overestimate the support of a spreading operator. Here, we improve the lightcone approach by assigning upper bounds that limit how much each error channel in the circuit can bias the expectation value. This set of bounds, which we refer to as a "shaded lightcone," enables a targeted application of PEC, improving the tradespace of bias and variance. We present an efficient algorithm that leverages the locality of errors to compute the bounds, providing a practical benefit even with modest classical resources. As an example, demonstrate the algorithm to the error mitigation of a 127-qubit Trotter circuit, reducing the sampling overhead by several orders of magnitude compared to PEC based on the causal lightcone.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_323,

title = {Stability of classical shadows under gate-dependent noise},

author = {Raphael Brieger and Markus Heinrich and Ingo Roth and Martin Kliesch},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_118,

title = {Tangling schedules eases hardware connectivity requirements for quantum error correction},

author = {Gyorgy Geher and Ophelia Crawford and Earl Campbell},

url = {https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.5.010348},

year  = {2024},

date = {2024-01-01},

abstract = {Error corrected quantum computers have the potential to change the way we solve computational problems. Quantum error correction involves repeated rounds of carefully scheduled gates to measure the stabilizers of a code. A set of scheduling rules is typically imposed on the order of gates to ensure that the circuit can be rearranged into an equivalent circuit that can be easily seen to measure the stabilizers. In this work, we ask what would happen if we break these rules and instead use circuit schedules that we describe as tangled. We find that tangling schedules generates long-range entanglement not accessible using nearest-neighbor two-qubit gates. Our tangled-schedule method provides a new tool for building quantum error-correction circuits and we explore applications to design new architectures for fault-tolerant quantum computers. Notably, we show that, for the widely used Pauli-based model of computation (achieved by lattice surgery), this access to longer-range entanglement can reduce the device connectivity requirements, without compromising on circuit depth.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_202,

title = {The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels},

author = {Alessandro Falco and Giacomo De Palma},

year  = {2024},

date = {2024-01-01},

abstract = {We prove the multimode conditional quantum Entropy Power Inequality for bosonic quantum systems. This inequality determines the minimum conditional von Neumann entropy of the output of the most general linear mixing of bosonic quantum modes among all the input states of the modes with given conditional entropies. Bosonic quantum systems constitute the mathematical model for the electromagnetic radia- tion in the quantum regime, which provides the most promising platform for quantum communication and quantum key distribution. We apply our multimode conditional Entropy Power Inequality to determine new lower bounds to the squashed entanglement of a large family of bosonic quantum Gaussian states. The squashed entanglement is one of the main entanglement measures in quantum communication theory, providing the best known upper bound to the distillable key. Exploiting this result, we determine a new lower bound to the squashed entanglement of the multimode bosonic Gaussian channels that are extreme, i.e., that cannot be decomposed as a non-trivial convex combination of quantum channels. The squashed entanglement of a quantum channel provides an upper bound to its secret-key capacity, i.e., the capacity to generate a secret key shared between the sender and the receiver.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_113,

title = {Time discretization of near-adiabatic quantum dynamics with a large time step size},

author = {Dong An and Pedro C. S. Costa and Dominic W. Berry},

year  = {2024},

date = {2024-01-01},

abstract = {Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. Here we establish general methodology of analyzing various numerical methods for discretizing near-adiabatic quantum dynamics. According to our analysis, the time step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, even first-order Trotter with uniform time step size can achieve exponential convergence. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterrized adiabatic approach: it can match the Grover lower bound, it does not require a priori knowledge on the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm.},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_410,

title = {Transition of Anticoncentration in Gaussian Boson Sampling},

author = {Adam Ehrenberg and Joseph Iosue and Abhinav Deshpande and Dominik Hangleiter and Alexey Gorshkov},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Thursday},

pubstate = {published},

tppubtype = {Poster}

}

@Poster{P24_283,

title = {Unified frameworks for uniform continuity of entropic quantities},

author = {Andreas Bluhm and Ángela Capel and Paul Gondolf and Tim Möbus and Antonio Pérez Hernández},

year  = {2024},

date = {2024-01-01},

keywords = {Outstanding Poster, Poster session Monday},

pubstate = {published},

tppubtype = {Poster}

}