Accepted talks

@Talk{T24_234,

title = {(Quantum) complexity of testing signed graph clusterability},

author = {Kuo-Chin Chen and Simon Apers and Min-Hsiu Hsieh},

year  = {2024},

date = {2024-01-01},

abstract = {This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity $tildeO(N^1/3)$ for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an $tildeØmega(sqrtN)$ classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.},

keywords = {Other, Proceedings, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@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_325,

title = {A shortcut to a near-optimal quantum linear system solver},

author = {Alexander Dalzell},

year  = {2024},

date = {2024-01-01},

abstract = {Given a linear system of equations Ax = b, quantum linear system solvers (QLSSs) approximately prepare a quantum state |x⟩ for which the amplitudes are proportional to the solution vector x. Asymptotically optimal QLSSs have query complexity O(κlog(1/ε)), where κ is the condition number of A, and ε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant factors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple, near-optimal QLSS that does not use these techniques. If the solution norm ∥x∥∥A∥/∥b∥ is known exactly, our QLSS requires only a single application of kernel reflection (an extension of eigenstate filtering), and has query complexity (1 + O(ε))κ ln(2√2/ε). If the norm is not known, it can be estimated up to a constant factor using O(log log(κ)) applications of kernel projection (a slight generalization of eigenstate filtering), yielding a QLSS with near-optimal total complexity O(κ log log(κ) log log log(κ) + κ log(1/ε)). Preliminary constant-factor analysis suggests that for practical values of κ, ε our QLSS provides rigorous guarantees that are at least an order of magnitude better than previous guarantees.},

keywords = {Quantum algorithms},

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_62,

title = {An improved Quantum Max Cut approximation via Maximum Matching},

author = {Eunou Lee and Ojas Parekh},

year  = {2024},

date = {2024-01-01},

abstract = {Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee (0.562, generic input graph) and King (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms},

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

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_26,

title = {Classical Verification of Quantum Learning},

author = {Matthias C. Caro and Marcel Hinsche and Marios Ioannou and Alexander Nietner and Ryan Sweke},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning by Goldwasser et al. (ITCS 2021), we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_299,

title = {Clifford operations and homological codes for rotors and oscillators},

author = {Yijia Xu and Yixu Wang and Victor V. Albert},

year  = {2024},

date = {2024-01-01},

abstract = {We develop quantum information processing primitives for the planar rotor, the state space of a particle on a circle. By interpreting rotor wavefunctions as periodically identified wavefunctions of a harmonic oscillator, we determine the group of bosonic Gaussian operations inherited by the rotor. This (n)-rotor Clifford group, (textU(1)^n(n+1)/2 rtimes textGL_n(mathbbZ)), is represented by continuous (textU(1)) gates generated by polynomials quadratic in angular momenta, as well as discrete (textGL_n(mathbb Z)) momentum sign-flip and sum gates. We classify homological rotor error-correcting codes arXiv:2303.13723 and various rotor states based on equivalence under Clifford operations. Reversing direction, we map homological rotor codes and rotor Clifford operations back into oscillators by interpreting occupation-number states as rotor states of non-negative angular momentum. This yields new multimode homological bosonic codes protecting against dephasing and changes in occupation number, along with their corresponding encoding and decoding circuits. In particular, we show how to non-destructively measure the oscillator phase using conditional occupation-number addition and post selection. We also outline several rotor and oscillator varieties of the GKP-stabilizer codes arXiv:1903.12615.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_120,

title = {Concatenate codes, save qubits},

author = {Satoshi Yoshida and Shiro Tamiya and Hayata Yamasaki},

year  = {2024},

date = {2024-01-01},

abstract = {The essential requirement for fault-tolerant quantum computation (FTQC) is the total protocol design to achieve a fair balance of all the critical factors relevant to its practical realization, such as the space overhead, the threshold, and the modularity. A major obstacle in realizing FTQC with conventional protocols, such as those based on the surface code and the concatenated Steane code, has been the space overhead, i.e., the required number of physical qubits per logical qubit. Protocols based on high-rate quantum low-density parity-check (LDPC) codes gather considerable attention as a way to reduce the space overhead, but problematically, the existing fault-tolerant protocols for such quantum LDPC codes sacrifice the other factors. Here we construct a new fault-tolerant protocol to meet these requirements simultaneously based on more recent progress on the techniques for concatenated codes rather than quantum LDPC codes, achieving a constant space overhead, a high threshold, and flexibility in modular architecture designs. In particular, under a physical error rate of 0.1%, our protocol reduces the space overhead to achieve the logical CNOT error rates $10^-10$ and $10^-24$ by more than 90% and 97%, respectively, compared to the protocol for the surface code. Furthermore, our protocol achieves the threshold of 2.4% under a conventional circuit-level error model, substantially outperforming that of the surface code. The use of concatenated codes also naturally introduces abstraction layers essential for the modularity of FTQC architectures. These results indicate that the code-concatenation approach opens a way to significantly save qubits in realizing FTQC while fulfilling the other essential requirements for the practical protocol design.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_298,

title = {Conditional independence of 1D Gibbs states with applications to efficient learning},

author = {Paul Gondolf and Samuel O. Scalet and Alberto Ruiz-de-Alarcón and Álvaro M. Alhambra and Ángela Capel},

year  = {2024},

date = {2024-01-01},

abstract = {We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information defined through the so-called Belavkin-Staszewski relative entropy. Our main result is the superexponential decay of various such measures, under the assumption that the spin chain Hamiltonian is translation-invariant. We use a recovery map associated with these definitions to sequentially construct tensor network approximations in terms of marginals of small (sub-logarithmic) size. This allows for representations of the state that can be learned efficiently from local measurements. We also prove an approximate factorization condition for the purity, from which it follows that the purity of the entire Gibbs state can be efficiently estimated to a small multiplicative error. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin-Staszewski relative entropy upon the application of a conditional expectation.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_8,

title = {Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits},

author = {Jonathan Allcock and Jinge Bao and João F. Doriguello and Alessandro Luongo and Miklos Santha},

year  = {2024},

date = {2024-01-01},

abstract = {We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by $|xrangle|branglemapsto |xrangle|bøplus f(x)rangle$ for $xın0,1^n$ and $bın0,1$, where $f$ is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register $|xrangle$, while the second is based on Boolean analysis and exploits different representations of $f$ such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices — Quantum Random Access Memory ($QRAM$) and Quantum Random Access Gate ($QRAG$) — of memory size $n$. The implementation based on one-hot encoding requires either $O(nłognłogłogn)$ ancillae and $O(nłogn)$ Fan-Out gates or $O(nłogn)$ ancillae and $6$ Global Tunable gates. On the other hand, the implementation based on Boolean analysis requires only $2$ Global Tunable gates at the expense of $O(n^2)$ ancillae.},

keywords = {Intersection of quantum information and machine learning, Models of quantum computation},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_176,

title = {Dissipation-enabled bosonic Hamiltonian learning via new information-propagation bounds},

author = {Tim Möbus and Andreas Bluhm and Matthias C. Caro and Albert H. Werner and Cambyse Rouzé},

year  = {2024},

date = {2024-01-01},

abstract = {Reliable quantum technology requires knowledge of the dynamics governing the underlying system. This problem of characterizing and benchmarking quantum devices or experiments in continuous time is referred to as the Hamiltonian learning problem. In contrast to multi-qubit systems, learning guarantees for the dynamics of bosonic systems have hitherto remained mostly unexplored. For m-mode Hamiltonians given as polynomials in annihilation and creation operators with modes arranged on a lattice, we establish a simple moment criterion in terms of the particle number operator which ensures that learning strategies from the finite-dimensional setting extend to the bosonic setting, requiring only coherent states and heterodyne detection on the experimental side. We then propose an enhanced procedure based on added dissipation that even works if the Hamiltonian time evolution violates this moment criterion: With high success probability it learns all coefficients of the Hamiltonian to accuracy ε using a total evolution time of O(ε−2 log(m)). Our protocol involves the experimentally reachable resources of projected coherent state preparation, dissipative regularization akin to recent quantum error correction schemes involving cat qubits stabilized by a nonlinear multi-photon driven dissipation process, and heterodyne measurements. As a crucial step in our analysis, we establish our moment criterion and a new Lieb-Robinson type bound for the evolution generated by an arbitrary bosonic Hamiltonian of bounded degree in the annihilation and creation operators combined with photon-driven dissipation. Our work demonstrates that a broad class of bosonic Hamiltonians can be efficiently learned from simple quantum experiments, and our bosonic Lieb-Robinson bound may independently serve as a versatile tool for studying evolutions on continuous variable systems.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_137,

title = {Efficient Algorithms for All Port-Based Teleportation Protocols},

author = {Adam Wills and Min-Hsiu Hsieh and Sergii Strelchuk},

year  = {2024},

date = {2024-01-01},

abstract = {We resolve the long-standing open problem of implementing port-based teleportation (PBT) efficiently in all regimes: both probabilistically and deterministically, either with maximally entangled resource state or an optimised resource state. Compared to previous PBT implementations, which are restricted to the deterministic setting, we are able to demonstrate an exponential improvement in the number of ancillas required, as well as polynomial improvements in the gate complexity (albeit in separate protocols). The framework we introduce to implement PBT is flexible enough to be generalisable to other cases of the pretty good measurement, which is useful in the case that the approach via Petz recovery is inefficient.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_423,

title = {Efficient Optimal Control of Open Quantum Systems},

author = {Wenhao He and Tongyang Li and Xiantao Li and Zecheng Li and Chunhao Wang and Ke Wang},

year  = {2024},

date = {2024-01-01},

abstract = {The optimal control problem for open quantum systems can be formulated as a time- dependent Lindbladian that is parameterized by a number of time-dependent control variables. Given an observable and an initial state, the goal is to tune the control variables so that the expected value of some observable with respect to the final state is maximized. In this paper, we present algorithms for solving this optimal control problem efficiently, i.e., having a poly-logarithmic dependency on the system dimension, which is exponentially faster than best-known classical algorithms. Our algorithms are hybrid, consisting of both quantum and classical components. The quantum procedure simulates time-dependent Lindblad evolution that drives the initial state to the final state, and it also provides access to the gradients of the objective function via quantum gradient estimation. The classical procedure uses the gradient information to update the control variables. At the technical level, we provide the first (to the best of our knowledge) simulation al- gorithm for time-dependent Lindbladians with an ℓ1-norm dependence. As an alternative, we also present a simulation algorithm in the interaction picture to improve the algorithm for the cases where the time-independent component of a Lindbladian dominates the time-dependent part. On the classical side, we heavily adapt the state-of-the-art classical optimization analysis to interface with the quantum part of our algorithms. Both the quantum simulation techniques and the classical optimization analyses might be of independent interest},

keywords = {Proceedings, Quantum algorithms, Quantum information theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_403,

title = {Efficient quantum circuits for port-based teleportation},

author = {Dmitry Grinko and Adam Burchardt and Maris Ozols},

year  = {2024},

date = {2024-01-01},

abstract = {Port-based teleportation (PBT) is a variant of quantum teleportation that, unlike the canonical protocol by Bennett et al., does not require a correction operation on the teleported state. Since its introduction by Ishizaka and Hiroshima in 2008, no efficient implementation of PBT was known. We close this long-standing gap using methods from representation theory, in particular, recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We describe efficient quantum circuits for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We provide two constructions based on different encodings of the so-called Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(n log(n)) space complexity, and a Yamanouchi encoding that achieves O(n^2) time and O(log(n)) space complexity, both for constant local dimension and target error. We also describe efficient circuits for preparing the optimal resource states.},

keywords = {Other, Quantum algorithms, Quantum communication, Quantum estimation and measurement, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_131,

title = {Efficient Quantum Simulation of Solid-State Materials via Pseudopotentials},

author = {Dominic Berry and Nicholas Rubin and Ahmed Elnabawy and Gabriele Ahlers and Eugene DePrince and Joonho Lee and Christian Gogolin and Ryan Babbush},

year  = {2024},

date = {2024-01-01},

abstract = {First-quantized plane-wave representations provide a very promising approach for quantum algorithms for solid state materials. Pseudopotentials provide a method of further reducing the complexity by avoiding the need to simulate highly localized core orbitals. The complicated functional form of pseudopotentials constitutes a major challenge for the design of quantum algorithms. In this work we provide new techniques to efficiently implement pseudopotentials in quantum algorithms, with orders of magnitude improvement in complexity. Our methods include a high-accuracy QROM interpolation of the exponential function, combined with QROM for the pseudopotential parameters and coherent arithmetic. Moreover, we generalize prior methods to enable the simulation of materials defined by non-cubic unit cells. Finally, we combine these techniques to estimate the resources for block encoding required for simulating commercially relevant instances of heterogeneous catalysis.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_393,

title = {Efficient soft-output decoders for the surface code},

author = {Nadine Meister and Christopher Pattison and John Preskill},

year  = {2024},

date = {2024-01-01},

abstract = {Decoders that provide an estimate of the probability of a logical failure conditioned on the error syndrome ("soft-output decoders") can reduce the overhead cost of fault-tolerant quantum memory and computation. In this work we construct efficient soft-output decoders for the surface code derived from the Minimum-Weight Perfect Matching and Union-Find decoders. We show that soft-output decoding can improve the performance of a "hierarchical code," a concatenated scheme in which the inner code is the surface code, and the outer code is a high-rate quantum low-density parity-check code. Alternatively, the soft-output decoding can improve the reliability of fault-tolerant circuit sampling by flagging those runs that should be discarded because the probability of a logical error is intolerably large.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_194,

title = {Eigenpath traversal by Poisson-distributed phase randomisation},

author = {Joseph Cunningham and Jérémie Roland},

year  = {2024},

date = {2024-01-01},

abstract = {We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance ε. In many cases the bounds given by our general theorems are optimal, giving a time complexity of O(1/Δ) with Δ the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the amount of problem-specific insight necessary. As two applications of our framework we obtain optimal scaling for the Grover problem (i.e. O(N^1/2) where N is the database size) and the Quantum Linear System Problem (i.e. O(κłog(1/ε)) where κ is the condition number and ε the error tolerance) by direct applications of our theorems.},

keywords = {Models of quantum computation, Proceedings, Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_274,

title = {Exponential learning advantages with conjugate states and minimal quantum memory},

author = {Robbie King and Kianna Wan and Jarrod McClean},

year  = {2024},

date = {2024-01-01},

abstract = {The ability of quantum computers to directly manipulate and analyze quantum states stored in quantum memory allows them to learn about aspects of our physical world that would otherwise be invisible given a modest number of measurements. Here we investigate a new learning resource which could be available to quantum computers in the future – measurements on the unknown state accompanied by its complex conjugate ρ⊗ρ*. For a certain shadow tomography task, we surprisingly find that measurements on only copies of ρ⊗ρ* can be exponentially more powerful than measurements on ρ⊗K, even for large K. This expands the class of exponential advantages using only a constant overhead quantum memory, or minimal quantum memory, and we provide a number of examples where the state ρ* is naturally available in both computational and physical applications. In addition, we precisely quantify the power of classical shadows on single copies under a generalized Clifford ensemble and give a class of quantities that can be efficiently learned. The learning task we study in both the single copy and quantum memory is physically natural and corresponds to real-space observables with a limit of bosonic modes, where it achieves an exponential improvement in detecting certain signals under a noisy background. In addition to quantifying a fundamentally new and powerful resource in quantum learning, we believe the advantage may find applications in improving quantum simulation, learning from quantum sensors, and uncovering new physical phenomena.},

keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_434,

title = {Fault tolerance of stabilizer channels},

author = {Michael Beverland and Vadym Kliuchnikov and Shilin Huang},

year  = {2024},

date = {2024-01-01},

abstract = {Stabilizer channels, which are stabilizer circuits that implement logical operations while mapping from an input stabilizer code to an output stabilizer code, are ubiquitous for fault tolerant quantum computing not just with surface codes, but with general LDPC codes and Floquet codes. We introduce a rigorous and general formalism to analyze the fault tolerance properties of any stabilizer channel under a broad class of noise models. We provide rigorous but easy-to-work-with definitions and algorithms for the fault distance and hook faults for stabilizer channels. The generalized notion of hook faults which we introduce, defined with respect to an arbitrary subset of the circuit's faults rather than a fixed phenomenological noise model, can be leveraged for fault-tolerant circuit design. Additionally, we establish necessary conditions such that channel composition preserves the fault distance. We apply our framework to design and analyze fault tolerant stabilizer channels for surface codes, revealing novel aspects of fault tolerant circuits.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_407,

title = {Fault-tolerant circuits from twisted quantum doubles – Quantum error correction beyond stabilizer and Clifford},

author = {Andreas Bauer},

year  = {2024},

date = {2024-01-01},

abstract = {We propose a family of explicit fault-tolerant geometrically local circuits realizing any abelian non-chiral topological phase. These circuits are constructed by relating them to discrete fixed-point path integrals, specifically the abelian Dijkgraaf-Witten state sum on a 3-dimensional cellulation, which is a spacetime representation of the twisted quantum double model. The resulting circuits are based on the well-known syndrome extraction circuit of the (qudit) toric code with $8$ controlled-$X$ gates per spacetime unit cell, into which we insert non-Pauli phase gates that implement the ``twist''. The overhead compared to the toric code is moderate, in contrast to the few known constructions for twisted abelian phases. The simplest example is a fault-tolerant circuit for the double-semion phase, which consists of $12$ controlled-$S$ gates in addition to the $8$ controlled-$X$ gates per spacetime unit cell. We also show that other architectures for the qudit toric code phase, like measurement-based topological quantum computation, or Floquet codes, can be equipped with phase gates implementing the twist. As a further result, we prove fault tolerance for a very general class of topological circuits that we call 1-form symmetric fixed-point circuits, which includes the circuits in this paper as well as the standard toric code, subsystem toric codes, measurement-based topological quantum computation, or the (CSS) honeycomb Floquet code. The noise model we use includes arbitrary local noise, including weakly correlated noise and non-Pauli noise, for which explicit fault-tolerance proofs might not exist in the literature to date. In the appendix we present a simple combinatorial procedure to define formulas for higher cup products on arbitrary cellulation, which might be interesting in its own right for the study of twisted gauge theory.},

keywords = {Intersection of quantum information and condensed-matter theory, Quantum error correction and fault-tolerant quantum computing},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_269,

title = {Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling},

author = {Pedro C. S. Costa and Philipp Schleich and Mauro Morales and Dominic W. Berry},

year  = {2024},

date = {2024-01-01},

abstract = {The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. Second, we demonstrate that a rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs, preventing a quantum speedup for PDEs. Third, we provide improved, tighter bounds on the error of Carleman linearisation. We show that providing a stability criterion independent of the discretisation can conflict with the use of the rescaling due to the difference between the max-norm and 2-norm.},

keywords = {Quantum algorithms},

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_33,

title = {Gaussian decomposition of magic states for matchgate computations},

author = {Joshua Cudby and Sergii Strelchuk},

year  = {2024},

date = {2024-01-01},

abstract = {Magic states, pivotal for universal quantum computation via classically simulable Clifford gates, often undergo decomposition into resourceless stabilizer states, facilitating simulation through classical means. This approach yields three operationally significant metrics: stabilizer rank, fidelity, and extent. We extend these methods to encompass Matchgate circuits (MGCs). We begin with an investigation into the algebraic constraints defining Gaussian states, marking the first explicit characterisation of these states. The explicit description of Gaussian states is pivotal to our methods for tackling all the simulation tasks. Central to our inquiry is the concept of Gaussian rank – a pivotal metric defining the minimum terms required for decomposing a quantum state into Gaussian constituents. This metric holds paramount significance in determining the runtime of rank-based simulations for matchgate circuits featuring magic state inputs. The absence of low-rank decompositions presents a formidable computational hurdle, thereby prompting a deeper examination of fermionic magic states. We find that the Gaussian rank of 2 instances of our canonical magic state is 4 under symmetry-restricted decompositions. Additionally, our numerical analysis suggests the absence of low-rank decompositions for 2 or 3 copies of this magic state. Further, we explore the Gaussian extent, a convex metric offering an upper bound on the rank. We prove the Gaussian extent's multiplicative behaviour on 4-qubit systems, along with initial strides towards proving its sub-multiplicative nature in general settings. One important result in that direction we present is an upper bound on the Gaussian fidelity of generic states.},

keywords = {Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_380,

title = {Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation},

author = {Amir Arqand and Thomas Hahn and Ernest Y. -Z. Tan},

year  = {2024},

date = {2024-01-01},

abstract = {The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore, it relies on the construction of an affine min-tradeoff function, which in practice can often be challenging to construct optimally. In this work, we address both of these challenges simultaneously by deriving a new entropy-accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as a convex optimization without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Rényi entropies if desired, yielding fully-Rényi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the framework of quantum probability estimation, and in the process we obtain some new results with respect to the latter framework as well.},

keywords = {Quantum cryptography, Quantum information 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_182,

title = {Hamiltonian Property Testing},

author = {Andreas Bluhm and Matthias C. Caro and Aadil Oufkir},

year  = {2024},

date = {2024-01-01},

abstract = {Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is in fact local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown Hamiltonian $H$ is $k$-local or ε-far from all $k$-local Hamiltonians, given access to the time evolution along $H$. First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require $TildeØmega(2^n)$ many time evolution queries and an expected total evolution time of $TildeØmega(2^n/ε)$, and even coherent testers need $Ømega(2^n/2)$ many queries and $Ømega(2^n/2/ε)$ total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.},

keywords = {Intersection of quantum information and machine learning, Quantum estimation and measurement},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_390,

title = {Hierarchical memories: Simulating quantum LDPC codes with local gates},

author = {Christopher Pattison and Anirudh Krishna and John Preskill},

year  = {2024},

date = {2024-01-01},

abstract = {Constant-rate low-density parity-check (LDPC) codes are promising candidates for constructing efficient fault-tolerant quantum memories. However, if physical gates are subject to geometric-locality constraints, it becomes challenging to realize these codes. In this paper, we construct a new family of [[N,K,D]] codes, referred to as hierarchical codes, that encode a number of logical qubits K = Omega(N/łog(N)^2). The N-th element of this code family is obtained by concatenating a constant-rate quantum LDPC code with a surface code; nearest-neighbor gates in two dimensions are sufficient to implement the corresponding syndrome-extraction circuit and achieve a threshold. Below threshold the logical failure rate vanishes superpolynomially as a function of the distance D(N). We present a bilayer architecture for implementing the syndrome-extraction circuit, and estimate the logical failure rate for this architecture. Under conservative assumptions, we find that the hierarchical code outperforms the basic encoding where all logical qubits are encoded in the surface code.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_439,

title = {How to fault-tolerantly realize any quantum circuit with local operations},

author = {Shin Ho Choe and Robert König},

year  = {2024},

date = {2024-01-01},

abstract = {We propose a new scheme for transforming a general quantum circuit into a geometrically local quantum circuit with polynomial qubit overhead and constant circuit depth overhead. We show that our scheme preserves fault-tolerance of the input quantum circuit under local stochastic noise. As a corollary, we show that our scheme can be used as a black box to transform any fault-tolerance construction involving non-local operation into one which only involves geometrically local operations. That is, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing. Applied to recent fault-tolerance constructions, this gives a fault-tolerance threshold theorem for universal quantum computations with local operations, a polynomial qubit overhead and a quasi-polylogarithmic depth overhead. A key element for our construction is parallel repetition of fault-tolerant long-range entanglement generation.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_233,

title = {Identity check problem for shallow quantum circuits},

author = {Sergey Bravyi and Natalie Parham and Minh Tran},

year  = {2024},

date = {2024-01-01},

abstract = {Checking whether two quantum circuits are approximately equivalent is a common task in quantum computing. We consider a closely related identity check problem: given a quantum circuit $U$, one has to estimate the diamond-norm distance between $U$ and the identity channel. We present a classical algorithm approximating the distance to the identity within a factor $alpha=D+1$ for shallow geometrically local $D$-dimensional circuits provided that the circuit is sufficiently close to the identity. The runtime of the algorithm scales linearly with the number of qubits for any constant circuit depth and spatial dimension. We also show that the operator-norm distance to the identity $|U-I|$ can be efficiently approximated within a factor $alpha=5$ for shallow 1D circuits and, under a certain technical condition, within a factor $alpha=2D+3$ for shallow $D$-dimensional circuits. A numerical implementation of the identity check algorithm is reported for 1D Trotter circuits with up to 100 qubits.},

keywords = {Other, Quantum information theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

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

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Intersection of quantum information and condensed-matter theory, Models of quantum computation, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Models of quantum computation, Quantum algorithms, Quantum information theory, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

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

pubstate = {published},

tppubtype = {Talk}

}

@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 = {Proceedings, Quantum error correction and fault-tolerant quantum computing},

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_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 = {Models of quantum computation, Quantum algorithms},

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_12,

title = {One-Wayness in Quantum Cryptography},

author = {Tomoyuki Morimae and Takashi Yamakawa},

year  = {2024},

date = {2024-01-01},

abstract = {The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Kretschmer, TQC 2021; Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental assumption in quantum cryptography? In this direction, [Brakerski, Canetti, and Qian, ITCS 2023] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions proposed by Morimae and Yamakawa. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results. 1. We define a weaker version of OWSGs, which we call weak OWSGs, and show that they are equivalent to OWSGs. It is a quantum analogue of the amplification theorem for classical weak one-way functions. 2. (Bounded-time-secure) quantum digital signatures with quantum public keys are equivalent to OWSGs. 3. Private-key quantum money schemes (with pure money states) imply OWSGs. 4. Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. For EFI pairs, single-copy security suffices. 5. We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statisticallyinvertible OWSGs, and show that they are equivalent to EFI pairs.},

keywords = {Proceedings, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_61,

title = {Online Locality Meets Distributed Quantum Computing},

author = {Amirreza Akbari and Xavier Coiteux-Roy and Francesco D'Amore and Francois Le Gall and Henrik Lievonen and Darya Melnyk and Augusto Modanese and Shreyas Pai and Marc-Olivier Renou and Václav Rozhoň and Jukka Suomela},

year  = {2024},

date = {2024-01-01},

abstract = {We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality $O(łog* n)$ in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the $Theta(łog* n)$ complexity class by using non-signaling arguments. Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for trees: if we can solve an LCL problem with locality $o(łog^(gapexp) n)$ in the randomized online-LOCAL model, we can solve it with locality $O(łog* n)$ in the classical deterministic LOCAL model. Put together, these results show that in trees the set of LCLs that can be solved with locality $O(łog* n)$ is the same across all these models: locality $O(łog* n)$ in quantum-LOCAL, non-signaling model, dynamic-LOCAL, or online-LOCAL is not stronger than locality $O(łog* n)$ in the classical deterministic LOCAL model.},

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

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_400,

title = {Permutation tests for quantum state identity},

author = {Harry Buhrman and Dmitry Grinko and Philip Verduyn Lunel and Jordi Weggemans},

year  = {2024},

date = {2024-01-01},

abstract = {The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether n unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of (fine-grained formulations of) the quantum state identity problem. Using tools from semi-definite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general G-test which uses an arbitrary subgroup G of S_n, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n-1 Swap tests.},

keywords = {Other, Quantum estimation and measurement, Quantum information 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_79,

title = {Preparation of Matrix Product States with Log-Depth Quantum Circuits},

author = {Daniel Malz and Georgios Styliaris and Zhi-Yuan Wei and J. Ignacio Cirac},

year  = {2024},

date = {2024-01-01},

abstract = {We consider the preparation of matrix product states (MPS) on quantum devices via quantum circuits of local gates. We first prove that faithfully preparing translation-invariant normal MPS of $N$ sites requires a circuit depth $T=Ømega(łog N)$. We then introduce an algorithm based on the renormalization-group transformation to prepare normal MPS with an error ε in depth $T=O(łog (N/epsilon))$, which is optimal. We also show that measurement and feedback leads to an exponential speedup of the algorithm, to $T=O(łogłog (N/epsilon))$. Measurements also allow one to prepare arbitrary translation-invariant MPS, including long-range non-normal ones, in the same depth. Finally, the algorithm naturally extends to inhomogeneous MPS.},

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

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_45,

title = {Provable Advantage in Quantum PAC Learning},

author = {Wilfred Salmon and Sergii Strelchuk and Tom Gur},

year  = {2024},

date = {2024-01-01},

abstract = {We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput. 1998, 28, 1136–1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution that generates the data is known. In the general case, it was recently shown by Arunachalam and de Wolf [JMLR, 19 (2018) 1-36] that quantum PAC learners can only achieve constant factor advantages over classical PAC learners. We show that with a natural extension of the definition of quantum PAC learning used by Arunachalam and de Wolf, we can achieve a generic advantage in quantum learning. To be precise, for any concept class $mathcalC$ of VC dimension $d$, we show there is an $(epsilon, delta)$-quantum PAC learner with sample complexity [ Ołeft(frac1sqrtepsilonłeft[d+ łog(frac1delta)right]łog^9(1/epsilon)right). ] Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity. We show the tightness of our result by proving an $Ømega(d/sqrtepsilon)$ lower bound that matches our upper bound up to polylogarithmic factors.},

keywords = {Quantum algorithms},

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_425,

title = {Quantum Bohnenblust–Hille inequalities and applications to learning low-degree quantum observables},

author = {Alexander Volberg and Haonan Zhang and Ohad Klein and Joseph Slote},

year  = {2024},

date = {2024-01-01},

abstract = {Analysis on the Boolean hypercube −1,1^n, particularly Fourier analysis, has played a crucial role in many areas of mathematics and computer science, including learning algorithms. In view of the success and importance of quantum algorithms, it is natural to transfer classical learning results to the quantum realm. In this contribution, we extend the recent progress on learning low-degree functions and quantum operators to the setting of general qudit systems, as well as develop novel Fourier-analytic tools for studying (generalized) Pauli decompositions of Hermitian operators. These tools also allow us to deduce new results in quantum Boolean analysis and approximate theory, such as the junta-type theorem and dimension-free discrete Remez-type inequalities.},

keywords = {Intersection of quantum information and machine learning, Quantum algorithms, Quantum estimation and measurement},

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_47,

title = {Quantum communication on the bosonic loss-dephasing channel},

author = {Francesco Anna Mele and Farzin Salek and Vittorio Giovannetti and Ludovico Lami},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum optical systems are typically affected by two types of noise: photon loss and dephasing. Despite extensive research on each noise process individually, a comprehensive understanding of their combined effect is still lacking. A crucial problem lies in determining the values of loss and dephasing for which the resulting loss-dephasing channel is anti-degradable, implying the absence of codes capable of correcting its effect or, alternatively, capable of enabling quantum communication. A conjecture in [Quantum 6, 821 (2022)] suggested that the bosonic loss-dephasing channel is anti-degradable if and only if the loss is above 50%. In this paper we refute this conjecture, specifically proving that for any value of the loss, if the dephasing is above a critical value, then the bosonic loss-dephasing channel is anti-degradable. While our result identifies a large parameter region where quantum communication is not possible, we also prove that if two-way classical communication is available, then quantum communication — and thus quantum key distribution — is always achievable, even for high values of loss and dephasing.},

keywords = {Quantum communication, Quantum information 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_124,

title = {Quantum computation of stopping power for inertial fusion target design},

author = {Nicholas Rubin and Dominic Berry and Alina Kononov and Fionn Malone and Tanuj Khattar and Alec White and Joonho Lee and Hartmut Neven and Ryan Babbush and Andrew Baczewski},

year  = {2024},

date = {2024-01-01},

abstract = {Stopping power is the rate at which a material absorbs the kinetic energy of a charged particle passing through it – one of many properties needed over a wide range of thermodynamic conditions in modeling inertial fusion implosions. First-principles stopping calculations are classically challenging because they involve the dynamics of large electronic systems far from equilibrium, with accuracies that are particularly difficult to constrain and assess in the warm-dense conditions preceding ignition. Here, we describe a protocol for using a fault-tolerant quantum computer to calculate stopping power from a first-quantized representation of the electrons and projectile. Our approach builds upon the electronic structure block encodings of Su et al. [PRX Quantum 2, 040332 2021], adapting and optimizing those algorithms to estimate observables of interest from the non-Born-Oppenheimer dynamics of multiple particle species at finite temperature. We also work out the constant factors associated with a novel implementation of a high-order Trotter approach to simulating a grid representation of these systems. Ultimately, we report logical qubit requirements and leading-order Toffoli costs for computing the stopping power of various projectile/target combinations relevant to interpreting and designing inertial fusion experiments. We estimate that scientifically interesting and classically intractable stopping power calculations can be quantum simulated with roughly the same number of logical qubits and about one hundred times more Toffoli gates than is required for state-of-the-art quantum simulations of industrially relevant molecules such as FeMoco or P450.},

keywords = {Quantum algorithms, Simulation of quantum systems},

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_281,

title = {Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits},

author = {Jiachen Hu and Tongyang Li and Xinzhao Wang and Yecheng Xue and Chenyi Zhang and Han Zhong},

year  = {2024},

date = {2024-01-01},

abstract = {We systematically investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed to estimate the mean μ, where the samples come from different random variables with mean close to μ. Technically, our quantum algorithms reduce bounded and sub-Gaussian random variables to the Bernoulli case, and use an uncomputation trick to overcome the challenge that direct amplitude estimation does not work with non-identical query access. Our quantum query lower bounds are established by simulating non-identical oracles by parallel oracles, and also by an adversarial method with non-identical oracles. Both results pave the way for proving quantum query lower bounds with non-identical oracles in general, which may be of independent interest.},

keywords = {Proceedings, Quantum algorithms},

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_354,

title = {Quantum Spherical Codes},

author = {Shubham P. Jain and Joseph T. Iosue and Alexander Barg and Victor V. Albert},

year  = {2024},

date = {2024-01-01},

abstract = {We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise.},

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

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_237,

title = {Quantum state tomography of continuous variable systems},

author = {Francesco Anna Mele and Salvatore F. E. Oliviero and Lennart Bittel and Jens Eisert and Vittorio Giovannetti and Ludovico Lami and Lorenzo Leone and Antonio Anna Mele},

year  = {2024},

date = {2024-01-01},

abstract = {While quantum state tomography has been extensively analysed for qubit and qudit systems, rigorous performance guarantees in terms of ε-approximation in trace distance remain largely unexplored for continuous variable quantum systems, due to subtleties that arise in the infinite-dimensional context. This work addresses this gap. First, we discover that to learn energy-constrained n-mode states, the sample complexity must scale with ε as Ω(1/ε^(2n)). This is in sharp contrast with the n-qubit case, where the ε-scaling is O(1/ε^2) — thereby establishing the extreme inefficiency of continuous variable tomography. Remarkably, we prove that O(1/ε^(2n)) copies are both necessary and sufficient if we restrict to tomography of pure states. Second, we establish that Gaussian states can be efficiently learned, a result that has been previously assumed but never rigorously proved. To do that, we answer the following fundamental question for Gaussian quantum information: If we approximate the first moment and covariance matrix of an unknown Gaussian state with precision ε, what is the resulting trace distance error on the state? Third, we show how to efficiently learn states prepared by Gaussian unitaries and a few local non-Gaussian evolutions, unveiling more on the structure of these slightly non-Gaussian systems.},

keywords = {Quantum information 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_110,

title = {Reversing Unknown Quantum Processes via Virtual Combs: for Channels with Limited Information},

author = {Chengkai Zhu and Yin Mo and Yu-Ao Chen and Xin Wang},

year  = {2024},

date = {2024-01-01},

abstract = {The inherent irreversibility of quantum dynamics for open systems poses a significant barrier to the inversion of unknown quantum processes. To tackle this challenge, we propose the framework of virtual combs that exploit the unknown process iteratively with additional classical post-processing to simulate the process inverse. Notably, we demonstrate that an $n$-slot virtual comb can exactly reverse a depolarizing channel with one unknown noise parameter out of $n+1$ potential candidates, and a 1-slot virtual comb can exactly reverse an arbitrary pair of quantum channels. We further explore the approximate inversion of an unknown channel within a given channel set. A worst-case error decay of $cO(n^-1)$ is unveiled for depolarizing channels within a specified noise region. Moreover, we show that virtual combs can universally reverse unitary operations and investigate the trade-off between the slot number and the sampling overhead.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_192,

title = {Revocable Quantum Digital Signatures},

author = {Tomoyuki Morimae and Alexander Poremba and Takashi Yamakawa},

year  = {2024},

date = {2024-01-01},

abstract = {We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message ``0'' is done publicly, whereas the verification for the message ``1'' is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply ``returned'' and then verified as part of revocation. Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.},

keywords = {Proceedings, Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_228,

title = {Robustness of Fixed Points of Quantum Channels and Application to Approximate Quantum Markov Chains},

author = {Robert Salzmann and Bjarne Bergh and Nilanjana Datta},

year  = {2024},

date = {2024-01-01},

abstract = {We address the following question: Given a quantum channel and a quantum state which is almost a fixed point of the channel, can we find a new channel and a new state, which are respectively close to the original ones, such that they satisfy an exact fixed point equation? This question can be asked under many interesting constraints in which the original channel and state are assumed to have certain structures which the new channel and state are supposed to satisfy as well. We answer this question in the affirmative under fairly general assumptions on aforementioned structures through a compactness argument. We then concentrate on specific structures of states and channels and establish explicit bounds on the approximation errors between the original- and new states and channels respectively. We find a particularly desirable form of these approximation errors for a variety of interesting examples, including the structure of general quantum states and general quantum channels, unitary channels and unital channels. On the other hand, for the setup of bipartite quantum systems for which the considered channels are demanded to act locally, we are able to lower bound the possible approximation errors. Here, we show that these approximation errors necessarily scale in terms of the dimension of the quantum system in an undesirable manner. We apply our results to the robustness question of quantum Markov chains (QMC) and establish the following: For a tripartite quantum state we show the existence of a dimension-dependent upper bound on the distance to the set of QMCs, which decays as the conditional mutual information of the state vanishes.},

keywords = {Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_214,

title = {Secret Sharing with Certified Deletion},

author = {James Bartusek and Justin Raizes},

year  = {2024},

date = {2024-01-01},

abstract = {Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may not be a realistic assumption. We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret is split into quantum shares which can be verifiably destroyed. We define two natural notions of security: no-signaling security and adaptive security. Next, we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain high rate seedless extraction from certain quantum sources of entropy.},

keywords = {Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_230,

title = {Showcasing a Barren Plateau Theory Beyond the Dynamical Lie Algebra},

author = {Nahuel L. Diaz and Diego García-Martín and Sujay Kazi and Martin Larocca and Marco Cerezo},

year  = {2024},

date = {2024-01-01},

abstract = {Barren plateaus have emerged as a pivotal challenge for variational quantum computing. Our understanding of this phenomenon underwent a transformative shift with the recent introduction of a Lie algebraic theory capable of explaining most sources of barren plateaus. However, this theory requires either initial states or observables that lie in the circuit's Lie algebra. Focusing on parametrized matchgate circuits, in this work we are able to go beyond this assumption and provide an exact formula for the loss function variance that is valid for arbitrary input states and measurements. Our results reveal that new phenomena emerge when the Lie algebra constraint is relaxed. For instance, we find that the variance does not necessarily vanish inversely with the Lie algebra's dimension. Instead, this measure of expressivity is replaced by a generalized expressivity quantity: the dimension of the Lie group modules. By characterizing the operators in these modules as products of Majorana operators, we can introduce a precise notion of generalized globality and show that measuring generalized-global operators leads to barren plateaus. Our work also provides operational meaning to the generalized entanglement as we connect it with known fermionic entanglement measures, and show that it satisfies a monogamy relation. Finally, while parameterized matchgate circuits are not efficiently simulable in general, our results suggest that the structure allowing for trainability may also lead to classical simulability.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_444,

title = {Signal-Processing Phase Estimation against Time-dependent Errors},

author = {Connor Clayton and Yulong Dong and Murphy Yuezhen Niu and Shi Jie Samuel Tan},

year  = {2024},

date = {2024-01-01},

abstract = {Harnessing quantum effects in metrology, such as entanglement and coherence, enables enhanced sensitivity in measuring parameters. Despite this, decoherence and time-dependent errors can uNdermine Heisenberg-limited amplification. To navigate these challenges in realistic experiments for phase estimation of a two-level unitary gate, we introduce a suite of quantum metrology algorithms. These algorithms capitalize on the universality of quantum signal transformation to decouple two interdependent phase parameters into largely orthogonal ones, ensuring that time-dependent errors in one do not compromise the accuracy of learning the other. Our approach combines provably optimal classical estimation with nearly optimal quantum circuit design, achieving unparalleled accuracy of 10−4 radians in standard deviation for estimating extremely small angles in superconducting qubit experiments with low-depth (< 10) circuits. This accuracy surpasses existing alternatives by two orders of magnitude and is adaptable to ion trap gates. We prove both theoretically and numerically the optimality of our algorithm against time-dependent phase error in φ. Remarkably, in the low circuit depth limit, our method’s estimation variance on the time-sensitive parameter φ scales faster than the asymptotic Heisenberg limit as a function of depth, Var(φˆ) ∼ 1/d4. Crucially, our method’s efficacy is rigorously affirmed through an analysis against the quantum Fisher information. This analysis underpins our protocol’s ability to achieve unmatched precision, leveraging quantum resources more effectively than has been possible before.},

keywords = {Quantum estimation and measurement},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_146,

title = {Single-shot decoding of good quantum LDPC codes},

author = {Shouzhen Gu and Eugene Tang and Libor Caha and Shin Ho Choe and Zhiyang He and Aleksander Kubica},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum Tanner codes constitute a family of quantum low-density parity-check (LDPC) codes with good parameters, i.e., constant encoding rate and relative distance. In this work, we prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. Importantly, this result holds for both the adversarial and stochastic noise. In our analysis, we consider the sequential and parallel decoding algorithms introduced by Leverrier and Zemor. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_464,

title = {State Purification with Symmetry Subgroup Projectors},

author = {Bo Yang and Elham Kashefi and Dominik Leichtle and Harold Ollivier},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity. This is an essential building block for the near- and middle-term quantum ecosystems before the availability of full fault tolerance, where one may want to obtain purified quantum states instead of expectation values. We propose an effective state purification gadget with a moderate quantum overhead by projecting multiple noisy quantum inputs to their symmetry subspace defined by a set of projectors forming a subgroup of the symmetry group. This provides a state purification performance scaling inverse-linearly to the number of state copies given a fixed stochastic error rate, which drastically improves the implementation overhead in previous works. Our method may find its application in designing robust verification protocols for quantum outputs before the availability of fully fault-tolerant computing.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_58,

title = {Stochastic error cancellation in analog quantum simulation},

author = {Yiyi Cai and Yu Tong and John Preskill},

year  = {2024},

date = {2024-01-01},

abstract = {Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by small local perturbations, which are assumed to be random and unbiased. We analyze the error accumulated in observables in this setting and show that, due to stochastic error cancellation, with high probability the error scales as the square root of the number of qubits instead of linearly. We explore the concentration phenomenon of this error as well as its implications for local observables in the thermodynamic limit. Moreover, we show that stochastic error cancellation also manifests in the fidelity between the target state at the end of time-evolution and the actual state we obtain in the presence of noise. This indicates that, to reach a certain fidelity, more noise can be tolerated than implied by the worst-case bound if the noise comes from many statistically independent sources.},

keywords = {Proceedings, Simulation of quantum systems},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_343,

title = {Sufficiency of Rényi divergences},

author = {Niklas Galke and Lauritz Luijk and Henrik Wilming},

year  = {2024},

date = {2024-01-01},

abstract = {A set of classical or quantum states is equivalent to another one if there exists a pair of classical or quantum channels mapping either set to the other one. For dichotomies (pairs of states), this is closely connected to (classical or quantum) Rényi divergences (RD) and the data-processing inequality: If a RD remains unchanged when a channel is applied to the dichotomy, then there is a recovery channel mapping the image back to the initial dichotomy. Here, we prove for classical dichotomies that equality of the RDs alone is already sufficient for the existence of a channel in any of the two directions and discuss some applications. In the quantum case, all families of quantum RDs are seen to be insufficient because they cannot detect anti-unitary transformations. Thus, including anti-unitaries, we pose the problem of finding a sufficient family. It is shown that the Petz and maximal quantum RD are still insufficient in this more general sense and we provide evidence for sufficiency of the minimal quantum RD. As a side result of our techniques, we obtain an infinite list of inequalities fulfilled by the classical, the Petz quantum, and the maximal quantum RDs. These inequalities are not true for the minimal quantum RDs. Our results further imply that any sufficient set of conditions for state transitions in the resource theory of athermality must be able to detect time-reversal.},

keywords = {Quantum communication, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_317,

title = {Taming Quantum Time Complexity},

author = {Aleksandrs Belovs and Stacey Jeffery and Duyal Yolcu},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (emphexactness). Second, through careful accounting (emphthriftiness), the total query complexity is smaller if subroutines are mostly run on cheaper inputs – a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining emphquantum Las Vegas query complexity. Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum emphtime complexity. In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, $Q(fcirc g)=ØO(Q(f)cdot Q(g))$, without log factors. We achieve this by employing a novel approach to the design of quantum algorithms based on what we call emphtransducers, and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.},

keywords = {Quantum algorithms},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_222,

title = {The Quantum Decoding Problem},

author = {André Chailloux and Jean-Pierre Tillich},

year  = {2024},

date = {2024-01-01},

abstract = {One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution (SIS) problem to the Learning with Errors (LWE) problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry[CLZ22] that this reduction can be made more powerful by replacing the LWE problem with a quantum equivalent, where the errors are given in quantum superposition. In parallel, Regev's reduction has recently been adapted in the context of code-based cryptography by Debris, Remaud and Tillich[DRT23], who showed a reduction between the Short Codeword Problem and the Decoding Problem (the DRT reduction). This motivates the study of the Quantum Decoding Problem (QDP), which is the Decoding Problem but with errors in quantum superposition and see how it behaves in the DRT reduction. The purpose of this paper is to introduce and to lay a firm foundation for QDP. We first show QD Pis likely to be easier than classical decoding, by proving that it can be solved in quantum polynomial time in a large regime of noise whereas no non-exponential quantum algorithm is known for the classical decoding problem. Then, we show that QDP can even be solved (albeit not necessarily efficiently) beyond the information theoretic Shannon limit for classical decoding. We give precisely the largest noise level where we can solve QDP giving in a sense the information theoretic limit for this new problem. Finally, we study how QDP can be used in the DRT reduction. First, we show that our algorithms can be properly used in the DRT reduction showing that our quantum algorithms for QDP beyond Shannon capacity can be used to find minimal weight codewords in a random code. On the negative side, we show that the DRT reduction cannot be, in all generality, a reduction between finding small codewords and QDP by exhibiting quantum algorithms for QDP where this reduction entirely fails. Our proof techniques include the use of specific quantum measurements, such as q-ary unambiguous state discrimination and pretty good measurements as well as strong concentration bounds on weight distribution of random shifted dual codes, which we relate using quantum Fourier analysis.},

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

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_431,

title = {The Quantum Esscher Transform},

author = {Yixian Qiu and Kelvin Koor and Patrick Rebentrost},

year  = {2024},

date = {2024-01-01},

abstract = {The Esscher Transform is a tool of broad utility in various domains of applied probability. It provides the solution to a constrained minimum relative entropy optimization problem. In this work, we study the generalization of the Esscher Transform to the quantum setting. We examine a relative entropy minimization problem for a quantum density operator, potentially of wide relevance in quantum information theory. The resulting solution form motivates us to define the quantum Esscher Transform, which subsumes the classical Esscher Transform as a special case. Envisioning potential applications of the quantum Esscher Transform, we also discuss its implementation on fault-tolerant quantum computers. Our algorithm is based on the modern techniques of block-encoding and quantum singular value transformation (QSVT). We show that given block-encoded inputs, our algorithm outputs a subnormalized block-encoding of the quantum Esscher transform within accuracy ε in $tilde O(kappa d łog^2 1/epsilon)$ queries to the inputs, where κ is the condition number of the input density operator and $d$ is the number of constraints.},

keywords = {Quantum algorithms, Quantum information theory},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_373,

title = {Toward a 2D Local Implementation of Quantum LDPC Codes},

author = {Noah Berthusen and Dhruv Devulapalli and Eddie Schoute and Andrew Childs and Michael Gullans and Alexey Gorshkov and Daniel Gottesman},

year  = {2024},

date = {2024-01-01},

abstract = {Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes which affects code performance and ease of physical realization. For device architectures restricted to 2D local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive amounts of overhead. In this work, we present an error correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of quasi-cyclic qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast local operations and classical communication (LOCC) routing. Through circuit-level simulations, we find that in some parameter regimes quasi-cyclic codes implemented with this protocol have logical error rates comparable to copies of the surface codes while using fewer physical qubits.},

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

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_59,

title = {Trained quantum neural networks are Gaussian processes},

author = {Filippo Girardi and Giacomo De Palma},

year  = {2024},

date = {2024-01-01},

abstract = {We study quantum neural networks made by parametric one-qubit gates and fixed two-qubit gates in the limit of infinite width, where the generated function is the expectation value of the sum of single-qubit observables over all the qubits. First, we prove that the probability distribution of the function generated by the untrained network with randomly initialized parameters converges in distribution to a Gaussian process whenever each measured qubit is correlated only with few other measured qubits. Then, we analytically characterize the training of the network via gradient descent with square loss on supervised learning problems. We prove that, as long as the network is not affected by barren plateaus, the trained network can perfectly fit the training set and that the probability distribution of the function generated after training still converges in distribution to a Gaussian process. Finally, we consider the statistical noise of the measurement at the output of the network and prove that a polynomial number of measurements is sufficient for all the previous results to hold and that the network can always be trained in polynomial time.},

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

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}

}

@Talk{T24_263,

title = {Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World},

author = {Alper Çakan and Vipul Goyal and Chen-Da Liu-Zhang and João Ribeiro},

year  = {2024},

date = {2024-01-01},

abstract = {Can an adversary hack into our computer and steal sensitive data such as cryptographic keys? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect hacking attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world? We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the leakage-resilient cryptography literature. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against. As a notable example, the most well-studied leakage model is that of bounded leakage, where it is assumed that an adversary learns at most L bits of leakage on secret components, for some leakage bound L. Although this leakage bound is necessary, many real-world side-channel attacks cannot be captured by bounded leakage. In this work, we design cryptographic schemes that provide guarantees against arbitrary side-channel attacks: - Using techniques from unclonable quantum cryptography, we design several basic leakage-resilient primitives, such as public- and private-key encryption, (weak) pseudorandom functions, and digital signatures which remain secure under (polynomially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classical information. Notably, the leakage-resilience of our schemes holds even in the stronger ``LOCC leakage'' model where the adversary can obtain adaptive leakage for (polynomially) emphunbounded number of rounds. - What if the adversary simply breaks in and obtains unbounded quantum leakage (thus making leakage-resilience impossible)? Going beyond leakage, what if the adversary can even tamper with the data arbitrarily? We initiate the study of intrusion-detection in the quantum setting, where one would like to detect if security has been compromised even in the face of an arbitrary intruder attack which can leak and tamper with classical as well as quantum data. We design cryptographic schemes supporting intrusion detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion.},

keywords = {Quantum cryptography},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_316,

title = {Virtual Channel Purification},

author = {Zhenhuan Liu and Xingjian Zhang and Yue-Yang Fei and Zhenyu Cai},

year  = {2024},

date = {2024-01-01},

abstract = {Quantum error mitigation is a key approach for extracting target state properties on state-of-the-art noisy machines and early fault-tolerant devices. Using the ideas from flag fault tolerance and virtual state purification, we develop the virtual channel purification (VCP) protocol, which consumes similar qubit and gate resources as virtual state purification but offers up to exponentially stronger error suppression with increased system size and more noisy operation copies. Furthermore, VCP removes most of the assumptions required in virtual state purification. Essentially, VCP is the first quantum error mitigation protocol that does not require specific knowledge about the noise models, the target quantum state, and the target problem while still offering rigorous performance guarantees for practical noise regimes. Further connections are made between VCP and quantum error correction to produce one of the first protocols that combine quantum error correction and quantum error mitigation beyond concatenation. We can remove all noise in the channel while paying only the same sampling cost as low-order purification, reaching beyond the standard bias-variance trade-off in quantum error mitigation. Our protocol can also be adapted to key tasks in quantum networks like channel capacity activation and entanglement distribution.},

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

pubstate = {published},

tppubtype = {Talk}

}