Accepted talks

@Talk{T24_208,

title = {A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits},

author = {Libor Caha and Xavier Coiteux-Roy and Robert Koenig},

year  = {2024},

date = {2024-01-01},

abstract = {We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D, even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or when ignoring locality constraints. By overcoming these limitations, we are thus proposing the strongest unconditional, fault-tolerant quantum-advantage demonstration to date. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.},

keywords = {Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_235,

title = {A Computational Tsirelson's Theorem for the Value of Compiled XOR Games},

author = {David Cui and Giulio Malavolta and Arthur Mehta and Anand Natarajan and Connor Paddock and Simon Schmidt and Michael Walter and Tina Zhang},

year  = {2024},

date = {2024-01-01},

abstract = {Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a "nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.},

keywords = {Other, Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_288,

title = {A Direct Reduction from the Polynomial to the Adversary Method},

author = {Aleksandrs Belovs},

year  = {2024},

date = {2024-01-01},

abstract = {The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.},

keywords = {Proceedings, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_417,

title = {An area law for the maximally-mixed ground state in arbitrarily degenerate systems with good AGSP},

author = {Itai Arad and Raz Firanko and Rahul Jain},

year  = {2024},

date = {2024-01-01},

abstract = {We show an area law in the mutual information for the maximally-mixed state Ω in the ground space of general Hamiltonians, which is independent of the underlying ground space degeneracy. Our result assumes the existence of a `good' approximation to the ground state projector (a good AGSP), a crucial ingredient in former area-law proofs. Such approximations have been explicitly derived for 1D gapped local Hamiltonians and 2D frustration-free and locally-gapped local Hamiltonians. As a corollary, we show that in 1D gapped local Hamiltonians, for any $eps>0$ and any bi-partition $Lcup L^c$ of the system, beginalign* I^eps_max(L:L^c)_Ømega łe bigO łog (|L|) + łog(1/eps), endalign* where $|L|$ represents the number of sites in $L$ and $I^eps_max(L:L^c)_Ømega$ represents the $eps$-emphsmoothed maximum mutual information with respect to the $L:L^c$ partition in Ω. From this bound we then conclude $I(L:L^c)_Ømega łe bigOłog(|L|)$ – an area law for the mutual information in 1D systems with a logarithmic correction. In addition, we show that Ω can be approximated up to an $eps$ in trace norm with a state of Schmidt rank of at most $poly(|L|/eps)$. Similar corollaries are derived for the mutual information of 2D frustration-free locally-gapped local Hamiltonians.},

keywords = {Intersection of quantum information and condensed-matter theory, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_437,

title = {An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut},

author = {Jun Takahashi and Chaithanya Rayudu and Cunlu Zhou and Robbie King and Kevin Thompson and Ojas Parekh},

year  = {2024},

date = {2024-01-01},

abstract = {Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMaxCut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.},

keywords = {Intersection of quantum information and condensed-matter theory, Quantum complexity theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_10,

title = {Gapped Clique Homology is QMA1-hard and contained in QMA},

author = {Robbie King and Tamara Kohler},

year  = {2024},

date = {2024-01-01},

abstract = {We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space X and an integer k, decide if X contains a k-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics [Wit82]. We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every k+1-clique in the graph to be a k-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is QMA1-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory [For94]. Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work [CK22]. Our result provides some suggestion that the quantum TDA algorithm [LGZ16] cannot be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.},

keywords = {Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_284,

title = {Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture},

author = {Jordi Weggemans and Marten Folkertsma and Chris Cade},

year  = {2024},

date = {2024-01-01},

abstract = {We study `Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call `Guidable Local Hamiltonian' problems. Unlike their guided counterparts, these problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We consider in particular two classes of guiding states: those that can be prepared efficiently by a quantum circuit; and those belonging to a class of quantum states we call classically evaluatable, for which it is possible to efficiently compute expectation values of local observables classically. We show that guidable local Hamiltonian problems for both classes of guiding states are $QCMA$-complete in the inverse-polynomial precision setting, but lie within $NP$ (or $NqP$) in the constant precision regime when the guiding state is classically evaluatable. Our completeness results show that, from a complexity-theoretic perspective, classical Ansätze selected by classical heuristics are just as powerful as quantum Ansätze prepared by quantum heuristics, as long as one has access to quantum phase estimation. In relation to the quantum PCP conjecture, we (i) define a complexity class capturing quantum-classical probabilistically checkable proof systems and show that it is contained in $BQP^NP[1]$ for constant proof queries; (ii) give a no-go result on `dequantizing' the known quantum reduction which maps a $QPCP$-verification circuit to a local Hamiltonian with constant promise gap; (iii) give several no-go results for the existence of quantum gap amplification procedures that preserve certain ground state properties; and (iv) propose two conjectures that can be viewed as stronger versions of the NLTS theorem. Finally, we show that many of our results can be directly modified to obtain similar results for the class $MA$.},

keywords = {Proceedings, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Quantum complexity theory, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Intersection of quantum information and machine learning, Other, Quantum complexity theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Quantum algorithms, Quantum communication, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_251,

title = {On the Role of Entanglement and Statistics in Learning},

author = {Srinivasan Arunachalam and Vojtech Havlicek and Louis Schatzki},

year  = {2024},

date = {2024-01-01},

abstract = {We make progress in understanding the relationship between learning models with access to entangled, separable and statistical measurements in the quantum statistical query (QSQ) model. We show the following results. Entangled versus separable measurements: The goal is to learn an unknown f from the concept class C containing functions from 0,1^n to [k] given copies of a uniform superposition over |x,f(x)>. We show that, if T copies suffice to learn f using entangled measurements, O(nT^2) copies suffice to learn f using only separable measurements. Entangled versus statistical measurements: The goal is to learn a function f in C given access to separable measurements or statistical measurements. We exhibit a concept class C based of degree-2 functions with exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise). This proves the "quantum analogue" of the seminal result of Blum et al. that separates classical SQ learning from classical PAC learning with classification noise. QSQ lower bounds for learning states: We introduce a quantum statistical query dimension (QSD), and use it to give lower bounds on the QSQ complexity of learning. We prove superpolynomial QSQ lower bounds for testing purity of quantum states, shadow tomography, learning coset states for the Abelian hidden subgroup problem, degree-2 functions, planted biclique states, and learning output states of Clifford circuits of depth polylog(n). We also show that an extension of QSD characterizes the complexity of general search problems. Further applications: We give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model. Prior works by Quek et al., Hinsche et al., and Nietner et al. proved analogous results assuming diagonal measurements and our work removes this assumption.},

keywords = {Intersection of quantum information and machine learning, Models of quantum computation, Quantum algorithms, Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_30,

title = {One Clean Qubit Suffices for Quantum Communication Advantage},

author = {Uma Girish and Srinivasan Arunachalam and Noam Lifshitz},

year  = {2024},

date = {2024-01-01},

abstract = {We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.},

keywords = {Models of quantum computation, Quantum algorithms, Quantum communication, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_249,

title = {Oracle separation of QMA and QCMA with bounded adaptivity},

author = {Shalev Ben-David and Srijita Kundu},

year  = {2024},

date = {2024-01-01},

abstract = {We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called slipperiness, which may be useful for getting a fully general classical oracle separation between QMA and QCMA.},

keywords = {Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_280,

title = {Parity vs. AC0 with simple quantum preprocessing},

author = {Joseph Slote},

year  = {2024},

date = {2024-01-01},

abstract = {A recent line of work has shown the unconditional advantage of constant-depth quantum computation, or QNC0, over NC0, AC0, and related models of classical computation. Problems exhibiting this advantage include search and sampling tasks related to the parity function, and it is natural to ask whether QNC0 can be used to help compute parity itself. Namely, we study AC0◦QNC0—a hybrid circuit model where AC0 operates on measurement outcomes of a QNC0 circuit—and we ask whether Par ∈ AC0◦QNC0. We believe the answer is negative. In fact, we conjecture AC0◦QNC0 cannot even achieve Ω(1) correlation with parity. As evidence for this conjecture, we prove the following: • When the QNC0 circuit is ancilla-free, we show this model can achieve only negligible correlation with parity, even when AC0 is replaced with any function having LMN-like decay in its Fourier spectrum. • For the general (non-ancilla-free) case, we show via a connection to nonlocal games that the conjecture holds for any class of postprocessing functions that has approximate degree o(n) and is closed under restrictions. Moreover, this is true even when the QNC0 circuit is given arbitrary quantum advice. By known results, this confirms the conjecture for linear-size AC0 circuits. • Another approach to proving the conjecture is to show a switching lemma for AC0◦QNC0. Towards this goal, we study the effect of quantum preprocessing on the decision tree complexity of Boolean functions. We find that from the point of view of a decision tree, nonlocal channels are no better than randomness: a Boolean function f precomposed with an n-party nonlocal channel is together equal to a randomized decision tree with depth no greater than DTdepth[f]. Taken together, our results suggest that while QNC0 is surprisingly powerful for search and sampling, that power is “locked away” in the global correlations of its output, inaccessible to simple classical computation for solving decision problems.},

keywords = {Models of quantum computation, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_82,

title = {Polynomial-Time Classical Simulation of Noisy IQP Circuits after Constant Depth},

author = {Joel Rajakumar and James Watson and Yi-Kai Liu},

year  = {2024},

date = {2024-01-01},

abstract = {Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer after a critical $O(1)$ depth. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit's architecture, on anti-concentration properties, nor do we require $Ømega(łog(n))$ circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought.},

keywords = {Models of quantum computation, Quantum complexity theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_257,

title = {Proper vs Improper Quantum PAC Learning},

author = {Ashwin Nayak and Pulkit Sinha},

year  = {2024},

date = {2024-01-01},

abstract = {A basic question in the PAC model of learning is whether proper learning is harder than improper learning. In the classical case, the answer to this question, with respect to sample complexity, is known to depend on the concept class. While there are concept classes for which the two modes of learning have the same complexity, there are examples of concept classes with VC dimension d that have sample complexity Ω ( d/ε log 1/ε) for proper learning with error ε, while the complexity for improper learning is O( d/ε). One such example arises from the Coupon Collector problem. Motivated by the efficiency of proper versus improper learning with quantum samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf [1] studied an analogue, the Quantum Coupon Collector problem. Curiously, they discovered that for learning size k subsets of [n] the problem has sample complexity Θ(k log min k, n − k + 1), in contrast with the complexity of Θ(k log k) for Coupon Collector. This effectively negates the possibility of a separation between the two modes of learning via the quantum problem, and Arunachalam et al. posed the possibility of such a separation as an open question. In this work, we first present an algorithm for the Quantum Coupon Collector problem with sample complexity that matches the sharper lower bound of (1 − o_k(1))k ln min k, n − k + 1 shown recently by Bab Hadiashar, Nayak, and Sinha [7], for the entire range of the parameter k. Next, we devise a variant of the problem, the Quantum Padded Coupon Collector. We prove that its sample complexity matches that of the classical Coupon Collector problem for both modes of learning, thereby exhibiting the same asymptotic separation between proper and improper quantum learning as mentioned above. The techniques we develop in the process can be directly applied to any form of padded quantum data. We hope that padding can more generally lift other forms of classical learning behaviour to the quantum setting.},

keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_86,

title = {Pseudoentanglement Ain't Cheap},

author = {Sabee Grewal and Vishnu Iyer and William Kretschmer and Daniel Liang},

year  = {2024},

date = {2024-01-01},

abstract = {We show that any pseudoentangled state ensemble with a gap of t bits of entropy requires Ω(t) non-Clifford gates to prepare, matching known lower bounds for pseudorandom state ensembles. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an n-qubit state that is stabilized by least 2^n-t Pauli operators, our algorithm produces an estimate that is within an additive factor of t/2 bits of the true entanglement entropy.},

keywords = {Quantum algorithms, Quantum complexity theory, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_71,

title = {Pseudorandom unitaries are neither real nor sparse nor noise-robust},

author = {Tobias Haug and Kishor Bharti and Dax Koh},

year  = {2024},

date = {2024-01-01},

abstract = {Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. In this study, we establish fundamental bounds on pseudorandomness. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers. Additionally, we derive lower bounds on the imaginarity and coherence of PRSs and PRUs, rule out the existence of sparse or real PRUs. We also show that the notions of PRS, PRUs and pseudorandom scramblers (PRSSs) are distinct in terms of resource requirements. We introduce the concept of pseudoresources, where states which contain a low amount of a given resource masquerade as high-resource states. We define pseudocoherence, pseudopurity and pseudoimaginarity, and identify three distinct types of pseudoresources in terms of their masquerading capabilities. Our work also establishes rigorous bounds on the efficiency of property testing, demonstrating the exponential complexity in distinguishing real quantum states from imaginary ones, in contrast to the efficient measurability of unitary imaginarity. Lastly, we show that the transformation from a complex to a real model of quantum computation is inefficient, in contrast to the reverse process, which is efficient. Our results establish fundamental limits on property testing and provide valuable insights into quantum pseudorandomness.},

keywords = {Quantum complexity theory, Quantum cryptography, Quantum estimation and measurement, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_73,

title = {Quantum 2-SAT on low dimensional systems is QMA_1-complete: Direct embeddings and black-box simulation},

author = {Dorian Rudolph and Sevag Gharibian and Daniel Nagaj},

year  = {2024},

date = {2024-01-01},

abstract = {Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a k-dimensional and l-dimensional qudit pair, denoted (k,l)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2,5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2,2)-QSAT (i.e. Quantum 2-SAT on qubits) is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3,d)-QSAT on the 1D line with d = O(1) is also QMA_1-hard. Finally, we initiate the study of (2,d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Omega(1/T^6) to Omega(1/T^2), for T the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian H on d'-dimensional qudits, we show how to embed it into an effective 1D (3,d)-QSAT instance, for d = O(1). Our approach may be viewed as a weaker notion of "simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result.},

keywords = {Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_4,

title = {Quantum Advantage from One-Way Functions},

author = {Tomoyuki Morimae and Takashi Yamakawa},

year  = {2024},

date = {2024-01-01},

abstract = {We demonstrate quantum advantage with several basic assumptions, specifically based on only the existence of OWFs. We introduce inefficient-verifier proofs of quantumness (IV-PoQ), and construct it from classical bit commitments. IV-PoQ is an interactive protocol between a verifier and a quantum prover consisting of two phases. In the first phase, the verifier is probabilistic polynomial-time, and it interacts with the prover. In the second phase, the verifier becomes inefficient, and makes its decision based on the transcript of the first phase. If the prover is honest, the inefficient verifier accepts with high probability, but any classical malicious prover only has a small probability of being accepted by the inefficient verifier. Our construction demonstrates the following results: (1)If one-way functions exist, then IV-PoQ exist. (2)If distributional collision-resistant hash functions exist (which exist if hard-on-average problems in SZK exist), then constant-round IV-PoQ exist. We also demonstrate quantum advantage based on worst-case-hard assumptions. We define auxiliary-input IV-PoQ (AI-IV-PoQ) that only require that for any malicious prover, there exist infinitely many auxiliary inputs under which the prover cannot cheat. We construct AI-IV-PoQ from an auxiliary-input version of commitments in a similar way, showing that (1)If auxiliary-input one-way functions exist (which exist if CZK⊈BPP), then AI-IV-PoQ exist. (2)If auxiliary-input collision-resistant hash functions exist (which is equivalent to PWPP⊈FBPP) or SZK⊈BPP, then constant-round AI-IV-PoQ exist.},

keywords = {Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_386,

title = {Quantum Circuits surpass Biased Threshold Circuits in Constant-Depth},

author = {Min-Hsiu Hsieh and Leandro Mendes and Michael Oliveira and Sathyawageeswar Subramanian},

year  = {2024},

date = {2024-01-01},

abstract = {Shallow-depth quantum circuits with gates of bounded fan-in have been demonstrated to achieve computational advantages over shallow-depth classical circuits, even allowing for unbounded fan-in (AC0). Despite their versatility, these computational models are known to be less powerful than Polynomial Threshold Function (PTF) circuits, which serve as a natural model for neural networks and exhibit enhanced expressivity and computational capabilities. We prove that PTF circuits with a constant number of layers, when biased (having the activation region of their gates limited), fail to solve certain computational (relational) problems that quantum circuits of constant depth can solve. Furthermore, we prove such a separation for a family of problems, one for each prime qudit dimension. We prove all of these separations via correlation bounds for average-case hardness. We also establish a tight lower bound on the size of biased PTF circuits that can solve a specific relational problem *exactly*. This allows us to significantly reduce the estimated resource requirements for potential demonstrations of quantum advantage. The main challenges in this area of research arise in establishing the classical lower bounds, and in designing non-local games with quantum-classical gaps in the winning strategy in order to go beyond qubits to higher dimensions. To address the former, we have formulated novel switching lemmas specifically designed for multi-output biased PTF circuits, and have developed a way to assess the difficulty of deriving exact solutions. Our contribution towards the latter is grounded in a novel assortment of non-local games, characterized by an exponential difference between their classical and quantum success probabilities. Finally, our technical developments could be of more general and independent interest.},

keywords = {Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_50,

title = {Quantum complexity theory meets TFNP: Product Quantum Satisfiability on qudits},

author = {Marco Aldi and Sevag Gharibian and Dorian Rudolph},

year  = {2024},

date = {2024-01-01},

abstract = {The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite being a classical complexity class, however, TFNP has made a surprise appearance in the study of Quantum Satisfiability (QSAT): If a QSAT instance has a System of Distinct Representatives (SDR), then it has a product-state solution [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Efficiently finding this product-state solution, however, has remained elusive. In this work, we introduce a new framework based on Weighted SDRs (WSDR), which among other results, allows us to: (1) significantly simplify and extend the results of [LLMSS 2010] to qudit systems, (2) establish a connection to the Bézout number for multihomogeneous polynomial systems, and (3) apply the parameterized algorithm of [Aldi, de Beaudrap, Gharibian, Saeedi 2021] to solve new instances of QSAT efficiently on qudits. The second of these, in particular, allows us to define the first "quantum-inspired" subclass of TFNP, for which we show QSAT with SDR is complete. Thus, we obtain the first evidence that QSAT with SDR is, in fact, intractable.},

keywords = {Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_121,

title = {Quantum delegation with an off-the-shelf device},

author = {Anne Broadbent and Arthur Mehta and Yuming Zhao},

year  = {2024},

date = {2024-01-01},

abstract = {Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.},

keywords = {Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_68,

title = {Quantum Generic Hardness for Discrete Logarithms and Integer Factorization},

author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},

year  = {2024},

date = {2024-01-01},

abstract = {We study the quantum computational complexity of the discrete logarithm (DL) problems and integer factorization in the context of ``generic algorithms''—that is, algorithms that do not exploit any properties of the group/ring encoding. We establish the generic models of quantum algorithms for group/ring problems as quantum analogs of their classical counterparts. In these models, we count the number of group/ring operations as complexity measures. Shor's and Regev's algorithms (or their slight modifications) can be described in these models. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and integer factorization in these models. * (The DL problem, fully quantum setting) We prove that any generic quantum DL algorithm must make a logarithmic number of group operations for the group size, showing that Shor's algorithm that makes the logarithmic number of group operations is asymptotically optimal regarding the number of group operations. This holds even considering parallel quantum algorithms. * (The DL problem, hybrid/memory-bounded setting) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We establish a model for generic hybrid quantum-classical algorithms and prove the matching lower bounds. We also study the memory-bounded setting and establish asymptotically tight lower bounds. We extend these results to the multiple-instance DL problem with a matching new algorithm. * (Integer factorization) We give a logarithmic lower bound for the order-finding algorithms, an important step for Shor's algorithm. We also prove a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev's algorithm.},

keywords = {Models of quantum computation, Quantum algorithms, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_218,

title = {Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians},

author = {Jordi Weggemans and Jonas Helsen and Harry Buhrman},

year  = {2024},

date = {2024-01-01},

abstract = {We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: - Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply emphuniformly at random, as long as it is allowed to do quantum pre-processing based on the input, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). - If the $q$-local Hamiltonian problem with constant promise gap can be solved in $QCMA$, then $QPCP[q] subseteq QCMA$ for any $q ın mO(1)$. - If $QMA(k)$ has a quantum PCP for any $k łeq poly(n)$, then $QMA(2) = QMA$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.},

keywords = {Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_348,

title = {Quantum State Learning Implies Circuit Lower Bounds},

author = {Nai-Hui Chia and Daniel Liang and Fang Song},

year  = {2024},

date = {2024-01-01},

abstract = {We establish connections between state tomography, pseudorandomness, state synthesis lower bounds, and classical circuit lower bounds. In particular, let C be a class of quantum states that can be prepared by a non-uniform family of poly-size quantum circuits. We show that if there exists an algorithm that, given copies of a quantum state, distinguishes whether it is in C or is Haar random, promised one of these is the case, that uses at most O(2^n^2) time and 2^n^0.99 samples then stateBQE is not a subset of stateC. Here stateBQE = stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by (Rosenthal and Yuen 2022), which capture problems with classical inputs but quantum output. We prove formally that efficient tomography implies an efficient distinguishing algorithm, so the ability to do sufficiently fast tomography also implies state synthesis lower bounds for C. Finally, combined with a result from (Rosenthal 2024), our result says that an O(2^n^2)-time and 2^n^0.99-sample algorithm that distinguishes QAC^0_f states from Haar random implies EXP is not a subset of TC^0, which would be a monumental breakthrough in classical circuit complexity. This help sheds light on why time-efficient learning algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results in (Arunachalam, Grilo, Gur, Oliveira, and Sundaram 2022) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes. For instance, just as they constructed a novel conditional pseudorandom generator secure against uniform sub-exponential-time quantum computations, we likewise construct a conditional pseudorandom state (ensemble) that is secure against uniform sub-exponential-time quantum computation and which relies on the complexity theoretic assumption that PSPACE is not a subset of BQSUBEXP. We also establish circuit size hierarchy theorems for non-uniform state synthesis and connections between state synthesis class separations and decision class separations, which may be of independent interest.},

keywords = {Intersection of quantum information and machine learning, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_243,

title = {Reversible Pebbling: Parallel Quantum Circuits with Low Amortized Space-Time Complexity},

author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee},

year  = {2024},

date = {2024-01-01},

abstract = {We introduce the parallel reversible pebbling game on directed graphs for constructing parallel quantum circuits that are efficient with respect to amortized space-time complexity (equivalently named cumulative complexity (CC)), a stronger metric than the conventional space-time complexity used for parallel algorithms. Our main result is a mapping from irreversible algorithms for computing a function, to quantum algorithms for computing the function in superposition, with just a sub-polynomial overhead in cumulative complexity. Thus, to construct a CC-efficient quantum oracle for a function, it suffices to solve the simpler problem of designing a CC-efficient classical algorithm for the function. This transformation also allows us to leverage the vast body of work on classical pebbling games for developing parallel quantum circuits with low amortized space-time complexity, given the data-dependency graph of the problem.},

keywords = {Quantum algorithms, Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_130,

title = {Tracial embeddable strategies: Lifting MIP* tricks to MIPco},

author = {Junqiao Lin},

year  = {2024},

date = {2024-01-01},

abstract = {We prove that any two-party correlation in the commuting operator model can be approximated using a tracial embeddable strategy, a class of strategy defined on a finite tracial von Neumann algebra, which we define in this paper. Using this characterization, we show that any approximately synchronous correlation can be approximated to the average of a collection of synchronous correlations in the commuting operator model. This generalizes the result from Vidick [JMP 2022] which only applies to finite-dimensional quantum correlations. As a corollary, we show that the quantum tensor code test from Ji et al. [FOCS 2022] follows the soundness property even under the general commuting operator model. Furthermore, we extend the state-dependent norm variant of the Gowers-Hatami theorem to finite von Neumann algebras. Combined with the aforementioned characterization, this enables us to lift many known results about robust self-testing for non-local games to the commuting operator model, including a sample efficient finite-dimensional EPR testing for the commuting operator strategies. We believe that, in addition to the contribution from this paper, this class of strategies can be helpful for further understanding non-local games in the infinite-dimensional setting.},

keywords = {Models of quantum computation, Other, Quantum complexity theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_15,

title = {Tradeoff Constructions for Quantum Locally Testable Codes},

author = {Adam Wills and Ting-Chun Lin and Min-Hsiu Hsieh},

year  = {2024},

date = {2024-01-01},

abstract = {In this work, we continue the search for quantum locally testable codes (qLTCs) of new parameters by presenting three constructions that can make new qLTCs from old. The first analyses the soundness of a quantum code under Hastings' weight reduction construction for qLDPC codes to give a weight reduction procedure for qLTCs. Secondly, we describe a novel `soundness amplification' procedure for qLTCs which can increase the soundness of any qLTC to a constant while preserving its distance and dimension, with an impact only felt on its locality. Finally, we apply the AEL distance amplification construction to the case of qLTCs for the first time which can turn a high-distance qLTC into one with linear distance, at the expense of other parameters. These constructions can be used on as-yet undiscovered qLTCs to obtain new parameters, but we also find a number of present applications to prove the existence of codes in previously unknown parameter regimes. In particular, applications of these operations to the hypersphere product code and the hemicubic code yield many previously unknown parameters. Additionally, soundness amplification can be used to produce the first asymptotically good testable quantum code (rather than locally testable) - that being one with linear distance and dimension, as well as constant soundness. Lastly, applications of all three results are described to an upcoming work.},

keywords = {Quantum complexity theory, Quantum error correction and fault-tolerant quantum computing},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_139,

title = {Two prover perfect zero knowledge for MIP*},

author = {Kieran Mastel and William Slofstra},

year  = {2024},

date = {2024-01-01},

abstract = {The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.},

keywords = {Quantum complexity theory, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}