Contributed Talks 2b

Abstract: Quantum computing introduces many well-motivated problems rooted in physics, asking to compute information from input quantum states. Identifying the computational hardness of these problems yields potential applications with far-reaching impacts across both the realms of computer science and physics. However, these new problems do not neatly fit within the scope of existing complexity theory. The standard classes primarily cater to problems with classical inputs and outputs, leaving a gap to characterize problems involving quantum states as inputs. For instance, breaking new quantum cryptographic primitives involves solving problems with quantum inputs; this significantly changes Impagliazzo’s five-world while the complexity classes central to Pessiland, Heuristica, and Algorithmica are grounded in problems with classical inputs and outputs. To bridge these knowledge gaps, we explore the complexity theory for quantum promise problems and potential applications. Quantum promise problems are quantum-input decision problems asking to identify whether input quantum states satisfy specific properties. We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, p/mQSZKhv, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE. This includes identifying complete problems, as well as proving containment and separation results among these classes. Here, p/mC denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C. Surprisingly, our findings uncover relationships that diverge from their classical analogues — specifically, we show unconditionally that p/mQIP \neq p/mPSPACE and p/mBQP/qpoly \neq p/mBQP/poly. This starkly contrasts the classical setting, where QIP=PSPACE and separations such as BQP/qpoly \neq BQP/poly are only known relative to oracles. This new framework has numerous applications in quantum cryptography, particularly in the contexts of Microcrypt and unconditional cryptography [Qia24, MNY24]. For Microcrypt, we provide a better characterization of its primitives; for example, we show that OWSG and PRS can be broken by a p/mQCMA oracle, leading to a natural quantum analogue of Impagliazzo’s five worlds by substituting the classical complexity classes in Pessiland, Heuristica, and Algorithmica with mBQP and mQCMA. Moreover, we establish the relativization barrier for proving the existence of EFI, noting that no such barrier currently exists within traditional complexity theory. For unconditional cryptography, our framework is the first to capture the notion of unconditional computational hardness, resolving the open problem in [Qia24,MNY24] by constructing an unconditionally secure auxiliary-input quantum commitment scheme with computational binding and statistical hiding. Our framework also has other applications in quantum property testing and unitary synthesis.

Abstract: One of the primary applications of classical Boltzmann machines is generative modeling, wherein the goal is to tune the parameters of a model distribution so that it closely approximates a target distribution. Training relies on estimating the gradient of the relative entropy between the target and model distributions, a task that is well understood when the classical Boltzmann machine has both visible and hidden units. For some years now, it has been an obstacle to generalize this finding to quantum state learning with quantum Boltzmann machines that have both visible and hidden units. In this paper, I derive an analytical expression for the gradient of the quantum relative entropy between a target quantum state and the reduced state of the visible units of a quantum Boltzmann machine. Crucially, this expression is amenable to estimation on a quantum computer, as it involves modular-flow-generated unitary rotations reminiscent of those appearing in my prior work on rotated Petz recovery maps. This leads to a quantum algorithm for gradient estimation in this setting. I then specialize the setting to quantum visible units and classical hidden units, and vice versa, and provide analytical expressions for the gradients, along with quantum algorithms for estimating them. Finally, I replace the quantum relative entropy objective function with the Petz--Tsallis relative entropy; here I develop an analytical expression for the gradient and sketch a quantum algorithm for estimating it, as an application of an independent derivation of a formula for the derivative of the matrix power function, which also involves modular-flow-generated unitary rotations. Ultimately, this paper demarcates progress in training quantum Boltzmann machines with visible and hidden units for generative modeling and quantum state learning.