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 = {Proceedings, Wednesday},

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

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

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 without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. 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 = {Tuesday},

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

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

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 = {Tuesday},

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 = {Monday, Proceedings},

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 = {Tuesday},

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 = {Monday},

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 = {Monday},

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 = {Monday},

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

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

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 = {Wednesday},

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

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

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. The n-rotor Clifford group, U(1)n(n+1)/2 ⋊ GLn(Z), is represented by continuous U(1) gates generated by polynomials quadratic in angular momenta, as well as discrete GLn(Z) gates generated by momentum sign-flip and sum gates. Understandings in rotor 

Clifford group allow us to establish connections between homological rotor error-correcting codes and oscillator quantum codes, including Gottesman-Kitaev-Preskill codes and rotation-symmetric bosonic codes. Inspired by homological rotor codes, we provide a systematic construction of multi-mode rotation-symmetric bosonic codes by analoging Fock states to rotor states with non-negative angular momentum. This new family of multi-mode bosonic codes protect against dephasing and changes in occupation numbers, which we call homological number-phase codes. Their encoding and decoding circuits are readily derived from the corresponding 

rotor Clifford operations. 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. 

References: arXiv:2311.07679, homological rotor error-correcting codes 

(arXiv:2303.13723), GKP-stabilizer codes (arXiv:1903.12615)},

keywords = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_120,

title = {Concatenate codes, save qubits},

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

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

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 = {Friday},

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

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

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. We prove that these measures decay super-exponentially, under the assumption that the spin chain Hamiltonian is translation-invariant. Using a recovery map associated with these measures, we sequentially construct tensor network approximations in terms of marginals of small (sub-logarithmic) size. As a main application, we show that classical representations of the states can be learned efficiently from local measurements with a polynomial sample complexity. We also prove an approximate factorization condition for the purity of the entire Gibbs state, which implies that it can be efficiently estimated to a small multiplicative error from a small number of local measurements. 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 = {Thursday},

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

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

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 x>|b> —> |x>|b+ f(x)> for x in 0,1^n and b in 0,1, where f is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register |x>, 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 log(n)łogłog(n)) ancillae and O(n log(n)) Fan-Out gates or O(n log(n)) 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 = {Monday},

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é},

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

year  = {2024},

date = {2024-01-01},

abstract = {In this work, we prove uniform continuity bounds for entropic quantities related to the sandwiched Rényi divergences such as the sandwiched Rényi conditional entropy. We follow three different approaches: The first one is the axiomatic approach, which exploits the sub-/ superadditivity and joint concavity/ convexity of the exponential of the divergence. In our second approach, termed the "operator space approach", we express the entropic measures as norms and utilize their properties for establishing the bounds. These norms draw inspiration from interpolation space norms. We not only demonstrate the norm properties solely relying on matrix analysis tools but also extend their applicability to a context that holds relevance in resource theories. By this, we extend the strategies of Marwah and Dupuis as well as Beigi and Goodarzi employed in the sandwiched Rényi conditional entropy context. Finally, we merge the approaches into a mixed approach that has some advantageous properties and then discuss in which regimes each bound performs best. Our results improve over the previous best continuity bounds or sometimes even give the first continuity bounds available. In a separate contribution, we use the ALAAF method, developed in a previous article by some of the authors, to study the stability of approximate quantum Markov chains.},

keywords = {Thursday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {Port-based teleportation (PBT) is a form of quantum teleportation in which no corrective unitary is required on the part of the receiver. Two primary regimes exist - deterministic PBT in which teleportation is always successful, but is imperfect, and probabilistic PBT, in which teleportation succeeds with probability less than one, but teleportation is perfect upon a success. Two further regimes exist within each of these in which the resource state used for the teleportation is fixed to a maximally entangled state, or free to be optimised. 

Recently, works resolved the long-standing problem of efficiently implementing port-based teleportation, tackling the two deterministic cases for qudits. Here, we provide algorithms in all four regimes for qubits. Emphasis is placed on the practicality of these algorithms, where we give polynomial improvements in the known gate complexity for PBT, as well as an exponential improvement in the required number of ancillas (albeit in separate protocols). Our approach to the implementation of the square-root measurement in PBT can be directly generalised to other highly symmetric state ensembles. For certain families of states, such a framework yields efficient algorithms in the case that the Petz recovery algorithm for the square-root measurement runs in exponential time.},

keywords = {Monday},

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, Wednesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_403,

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

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

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

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 by building on our recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We construct efficient quantum algorithms for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We describe two constructions based on different encodings of the Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(nlog(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 = {Monday},

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

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

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 = {Monday},

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

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

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 = {Wednesday},

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 = {Proceedings, Thursday},

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 = {Monday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_434,

title = {Fault tolerance of stabilizer channels},

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

url = {https://arxiv.org/pdf/2401.12017},

year  = {2024},

date = {2024-01-01},

abstract = {Stabilizer channels are stabilizer circuits that implement logical operations while mapping from an input stabilizer code to an output stabilizer code. They are widely used to implement fault tolerant error correction and logical operations in stabilizer codes such as surface codes and LDPC codes, and more broadly in subsystem, Floquet and space-time 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. This includes 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 a 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 = {Friday},

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

url = {https://arxiv.org/pdf/2403.12119},

year  = {2024},

date = {2024-01-01},

abstract = {We propose a family of explicit geometrically local circuits realizing any abelian non-chiral topological phase as an actively error-corrected fault-tolerant memory. 

These circuits are constructed from measuring 1-form symmetries in discrete fixed-point path integrals, which we express through cellular cohomology and higher-order cup products. 

The specific path integral we use is 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 a syndrome extraction circuit of the (qudit) stabilizer toric code, into which we insert non-Clifford phase gates that implement the ``twist''. 

The overhead compared to the toric code is moderate, in contrast to known constructions for twisted abelian phases. 

The simplest non-trivial example is a fault-tolerant circuit for the double-semion phase, defined on the same set of qubits as the stabilizer toric code, with $12$ controlled-$S$ gates in addition to the $8$ controlled-$X$ gates and $2$ single-qubit measurements of the toric code 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 enriched with phase gates to implement twisted quantum doubles instead of their untwisted versions. 

As a further result, we prove fault tolerance under arbitrary local (including non-Pauli) noise for a very general class of topological circuits that we call 1-form symmetric fixed-point circuits. 

This notion unifies the circuits in this paper as well as the stabilizer toric code, subsystem toric code, measurement-based topological quantum computation, or the (CSS) honeycomb Floquet code. We also demonstrate how our method can be adapted to construct fault-tolerant circuits for specific non-Abelian phases.},

keywords = {Tuesday},

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

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

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 apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. 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. An efficient solution may still be provided if the number of discretisation points is limited, as is possible when using higher-order discretisations.},

keywords = {Thursday},

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 = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_33,

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

author = {Joshua Cudby and Sergii Strelchuk},

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

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 simulation methods to encompass matchgate circuits (MGCs), and define equivalent metrics for this setting. 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 MGCs featuring magic state inputs. The absence of low-rank decompositions presents a 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 = {Wednesday},

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

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

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 can often be challenging to construct optimally in practice. 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 an intuitively interpretable convex optimization, without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Renyi entropies if desired, yielding fully-Renyi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the frameworks of quantum probability estimation or f-weighted Rényi entropies, and in the process we obtain some new results with respect to those frameworks as well.},

keywords = {Thursday},

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

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

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 𝖰𝖢𝖬𝖠-complete in the inverse-polynomial precision setting, but lie within 𝖭𝖯 (or 𝖭𝗊𝖯) 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 𝖰𝖯𝖢𝖯-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 𝖬𝖠.},

keywords = {Proceedings, Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_182,

title = {Hamiltonian Property Testing},

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

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

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 epsilon-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 at least order 2^n many time evolution queries and an expected total evolution time of order 2^n/epsilon, and even coherent testers need at least order 2^(n/2) many queries and order 2^(n/2)/epsilon 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 = {Thursday},

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

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

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 = {Thursday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {We show how to realize a general quantum circuit involving gates between arbitrary pairs of qubits by means of geometrically local quantum operations and efficient classical computation. We prove that circuit-level local stochastic noise modeling an imperfect implementation of our derived schemes is equivalent to local stochastic noise in the original circuit. Our constructions incur a constant-factor increase in the quantum circuit depth and a polynomial overhead in the number of qubits: To execute an arbitrary quantum circuit on n qubits, we give a 3D quantum fault-tolerance architecture involving O(n^3/2 log^3 n) qubits, and a quasi-2D architecture using O(n^2 log^3 n) qubits. 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. More generally, our transformation dispenses with the need for considering the locality of operations when designing schemes for fault-tolerant quantum information processing.},

keywords = {Friday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_233,

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

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

url = {https://arxiv.org/pdf/2401.16525},

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 = {Tuesday},

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

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

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 = {Thursday},

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 = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_81,

title = {Limits of noisy quantum metrology with restricted quantum controls},

author = {Sisi Zhou},

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

year  = {2024},

date = {2024-01-01},

abstract = {The Heisenberg limit (HL, with estimation error scales as 1/n) and the standard quantum limit (SQL, 1/sqrt(n)) are two fundamental limits in estimating an unknown parameter in n copies of quantum channels and are achievable with full quantum controls, e.g., quantum error correction (QEC). It is unknown though, whether these limits are still achievable in restricted quantum devices when QEC is unavailable, e.g., with only unitary controls or bounded system sizes. In this talk, I will discuss various new limits for estimating qubit channels under restrictive controls. The HL is proven to be unachievable in various cases, indicating the necessity of QEC in achieving the HL. Furthermore, a necessary and sufficient condition to achieve the SQL is determined, where a novel unitary control protocol is identified to achieve the SQL for certain types of noisy channels, and a constant floor on the estimation error is proven for other cases.},

keywords = {Monday},

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 = {Wednesday},

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 = {Monday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {The well-conditioned 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 its practical advantage 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 = {Monday},

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

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

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 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 application-inspired circuits demonstrates the method's scalability and performance. We show that the transpilation significantly reduces the circuit length on the set of circuits tested, and that the resulting circuit of multi-qubit gates has a further reduction in the expected circuit execution time compared to serial execution.},

keywords = {Proceedings, Wednesday},

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

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

year  = {2024},

date = {2024-01-01},

keywords = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_123,

title = {New Approaches to Complexity via Quantum Graphs},

author = {Eric Culf and Arthur Mehta},

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

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. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and 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 also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes NP, MA, QMA, and QMA(2). In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of QMA(k) to QMA(2) via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.},

keywords = {Wednesday},

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 = {Wednesday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {Motivated by realistic hardware considerations of the pre-fault-tolerant era, we comprehensively study the impact of uncorrected noise on quantum circuits. We first show that any noise `truncates' most quantum circuits to effectively logarithmic depth, in the task of computing Pauli expectation values. We then prove that quantum circuits under any non-unital noise exhibit lack of barren plateaus for cost functions composed of local observables. But, by leveraging the effective shallowness, we also design a classical algorithm to estimate Pauli expectation values within inverse-polynomial additive error with high probability over the ensemble. Its runtime is independent of circuit depth and it operates in polynomial time in the number of qubits for one-dimensional architectures and quasi-polynomial time for higher-dimensional ones. Taken together, our results showcase that, unless we carefully engineer the circuits to take advantage of the noise, it is unlikely that noisy quantum circuits are preferable over shallow quantum circuits for algorithms that output Pauli expectation value estimates, like many variational quantum machine learning proposals. Moreover, we anticipate that our work could provide valuable insights into the fundamental open question about the complexity of sampling from (possibly non-unital) noisy random circuits.},

keywords = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_132,

title = {On the Power of Quantum Distributed Proofs},

author = {Atsuya Hasegawa and Srijita Kundu and Harumichi Nishimura},

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

year  = {2024},

date = {2024-01-01},

abstract = {Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In dQMA protocols, with the help of quantum proofs and local communication, nodes on a network verify a 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. In this paper, we further investigate and characterize the power of the dQMA protocols for various decision problems. 

First, we give a more efficient dQMA 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 dQMA protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication protocols. Third, in a line network, we construct an efficient dQMA protocol for a problem that has an efficient two-party QMA communication protocol. Finally, we obtain the first lower bounds on the proof and communication cost of dQMA protocols. To prove a lower bound on the equality problem, we show any dQMA protocol with an entangled proof between nodes can be simulated with a dQMA protocol with a separable proof between nodes by using a QMA communication-complete problem introduced by Raz and Shpilka (CCC 2004).},

keywords = {Tuesday},

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

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

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 = {Tuesday},

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 = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_12,

title = {One-Wayness in Quantum Cryptography},

author = {Tomoyuki Morimae and Takashi Yamakawa},

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

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. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian 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. 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, weak OWSGs, and show that they are equivalent to OWSGs. (2) Quantum digital signatures 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. (5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.},

keywords = {Proceedings, Tuesday},

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

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

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(log⋆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 Θ(log⋆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 rooted trees: if we can solve an LCL problem with locality o(loglogn) in the randomized online-LOCAL model, we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. Put together, these results show that in rooted trees the set of LCLs that can be solved with locality O(log⋆n) is the same across all these models: classical deterministic and randomized LOCAL, quantum-LOCAL, non-signaling model, dynamic-LOCAL, and deterministic and randomized online-LOCAL.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_249,

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

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

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

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 = {Tuesday},

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 = {Monday},

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 = {Monday},

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 = {Monday},

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

url = {https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.132.040404},

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 (i.e., short-range correlated) MPS of N sites requires a circuit depth T = Ω(log N). We then introduce an algorithm based on the renormalization-group transformation to prepare normal MPS with an error ε in depth T = O[log(N/ε)]. The algorithm has thus the fastest scaling possible for this class of states. We also show that measurement and feedback leads to an exponential speedup of the algorithm to T = O[log log(N/ε)]. 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 = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_257,

title = {Proper vs Improper Quantum PAC Learning},

author = {Ashwin Nayak and Pulkit Sinha},

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

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, 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 (TQC 2020) 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 mink,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 mink,n−k+1 shown recently by Bab Hadiashar, Nayak, and Sinha (IEEE TIT 2024), 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 = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_45,

title = {Provable Advantage in Quantum PAC Learning},

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

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

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 [1]. 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 [2] 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 C of VC dimension d, we show there is an (ϵ,δ)-quantum PAC learner with sample complexity 

O(1/√ϵ[d+log(1/δ)]log^9(1/ϵ)). 

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 Ω(d/√ϵ) lower bound that matches our upper bound up to polylogarithmic factors. 

[1] SIAM J. Comput. 1998, 28, 1136-1153 [2] JMLR, 19 (2018) 1-36},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_86,

title = {Pseudoentanglement Ain't Cheap},

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

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

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. This bound is tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom functions exist. 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 at 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 = {Tuesday},

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

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

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. Further, we show that PRUs need imaginarity while PRS do not have this restriction. This implies that quantum randomness requires in general a complex-valued formalism of quantum mechanics, while for random quantum states real numbers suffice. Additionally, we derive lower bounds on the coherence of PRSs and PRUs, ruling out the existence of sparse PRUs and PRSs. 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 = {Wednesday},

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

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

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 = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_4,

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

author = {Tomoyuki Morimae and Takashi Yamakawa},

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

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 = {Tuesday},

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 = {Thursday},

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 = {Monday},

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

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

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 not anti-degradable if the loss is below $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 = {Wednesday},

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 = {Tuesday},

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 = {Thursday},

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

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

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 = {Thursday},

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

url = {https://arxiv.org/pdf/2307.03065 https://arxiv.org/pdf/2402.11269},

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 = {Thursday},

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

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

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, Tuesday},

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

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

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: (i) 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 uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the q-local Hamiltonian problem with constant promise gap can be solved in 𝖰𝖢𝖬𝖠, then 𝖰𝖯𝖢𝖯[q] is in 𝖰𝖢𝖬𝖠 for any constant q. (iii) If 𝖰𝖬𝖠(k) has a quantum PCP for any k=poly(n), then 𝖰𝖬𝖠(2) = 𝖰𝖬𝖠, 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 = {Monday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {I'll introduce a framework for constructing quantum codes defined on spheres, taking inspiration from classical spherical codes. The framework is applied 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, a property sufficient to guarantee protection against photon losses.},

keywords = {Tuesday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let C be a family of non-uniform quantum circuits of polynomial size and suppose that there exists an algorithm that, given copies of |ψ⟩, distinguishes whether |ψ⟩ is produced by C or is Haar random, promised one of these is the case. For arbitrary fixed constant c, we show that if the algorithm uses at most O(2^n^c) time and 2^n^0.99 samples then stateBQE⊄stateC. Here stateBQE:=stateBQTIME[2^O(n)] and stateC are state synthesis complexity classes as introduced by Rosenthal and Yuen (ITCS 2022), which capture problems with classical inputs but quantum output. Note that efficient tomography implies a similarly efficient distinguishing algorithm against Haar random states, even for nearly exponential-time algorithms. Because every state produced by a polynomial-size circuit can be learned with 2O(n) samples and time, or O(n^ω(1)) samples and 2^O(n^ω(1)) time, we show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis. Finally, a slight modification of our proof shows that distinguishing algorithms for quantum states can imply circuit lower bounds for decision problems as well. This help sheds light on why time-efficient tomography algorithms for non-uniform quantum circuit classes has only had limited and partial progress. Our work parallels results by Arunachalam et al. (FOCS 2021) that revealed a similar connection between quantum learning of Boolean functions and circuit lower bounds for classical circuit classes, but modified for the purposes of state tomography and state synthesis.},

keywords = {Friday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {Quantum state tomography, aimed at deriving a classical description of an unknown state from measurement data, is a fundamental task in quantum physics. In this work, we analyse the ultimate achievable performance of tomography of continuous-variable systems, such as bosonic and quantum optical systems. We prove that tomography of these systems is extremely inefficient in terms of time resources, much more so than tomography of qudit systems: the minimum number of state copies needed for tomography not only scales exponentially with the number of modes but also exhibits a dramatic scaling with the trace-distance error, even for low-energy states. On a more positive note, we prove that tomography of Gaussian states is efficient. To accomplish this, we answer a fundamental question for the field of continuous-variable quantum information: if we know with a certain error the first and second moments of an unknown Gaussian state, what is the resulting trace-distance error that we make on the state? Lastly, we demonstrate that tomography of non-Gaussian states prepared through Gaussian unitaries and a few local non-Gaussian evolutions is efficient and experimentally feasible.},

keywords = {Thursday},

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

url = {https://eprint.iacr.org/2024/334.pdf https://arxiv.org/pdf/2110.04191},

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 = {Wednesday},

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

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

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. Our research establishes a path to achieving the exact inverse of unknown channels with certain conditions, accompanied by a no-go theorem that underscores the intrinsic limitations imposed by quantum mechanics on such tasks. 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 inverse of an unknown channel within a given channel set. For any unknown depolarizing channels within a specified noise region, we unveil a worst-case error decay of O(n^−1) of reversing the channel via virtual combs. Moreover, we show that virtual combs with constant slots can be applied to universally reverse unitary operations and investigate the trade-off between the slot number and the sampling overhead.},

keywords = {Wednesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_192,

title = {Revocable Quantum Digital Signatures},

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

url = {https://arxiv.org/pdf/2312.13561},

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, Thursday},

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

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

year  = {2024},

date = {2024-01-01},

abstract = {Given a quantum channel and a state which satisfy a fixed point equation approx- 

imately (say, up to an error ε), can one find a new channel and a state, which are 

respectively close to the original ones, such that they satisfy an exact fixed point equa- 

tion? It is interesting to ask this question for different choices of constraints on the 

structures of the original channel and state, and requiring that these are also satisfied 

by the new channel and state. We affirmatively answer the above question, under 

fairly general assumptions on these structures, through a compactness argument. Ad- 

ditionally, for channels and states satisfying certain specific structures, we find explicit 

upper bounds on the distances between the pairs of channels (and states) in question. 

When these distances decay quickly (in a particular, desirable manner) as ε → 0, we 

say that the original approximate fixed point equation is rapidly fixable. We establish 

rapid fixability, not only for general quantum channels, but also when the original and 

new channels are both required to be unitary, mixed unitary or unital. In contrast, 

for the case of bipartite quantum systems with channels acting trivially on one subsys- 

tem, we prove that approximate fixed point equations are not rapidly fixable. In this 

case, the distance to the closest channel (and state) which satisfy an exact fixed point 

equation can depend on the dimension of the quantum system in an undesirable way. 

We apply our results on approximate fixed point equations to the question of robust- 

ness of quantum Markov chains (QMC) and establish the following: For any tripartite 

quantum state, there exists a dimension-dependent upper bound on its distance to the 

set of QMCs, which decays to zero as the conditional mutual information of the state vanishes.},

keywords = {Wednesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_214,

title = {Secret Sharing with Certified Deletion},

author = {James Bartusek and Justin Raizes},

url = {https://eprint.iacr.org/2024/736},

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 become an unrealistic 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 

s is split into quantum shares that can be destroyed in a manner verifiable by the dealer. 

 We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about s, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of s against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized. Next, we show that these security definitions are achievable: 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 better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.},

keywords = {Thursday},

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

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

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 expressiveness is replaced by a generalized expressiveness 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 = {Friday},

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, a feature lacking in prior art. This analysis underpins our protocol’s ability to achieve unmatched precision, leveraging quantum resources more effectively than has been possible before.},

keywords = {Monday},

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

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

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 article, we prove that quantum Tanner codes also facilitate single-shot quantum error correction (QEC) of adversarial noise, where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. We establish this result for both 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 = {Thursday},

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 = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_58,

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

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

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

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, Thursday},

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 = {Thursday},

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 = {Thursday},

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, Tuesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_431,

title = {The Quantum Esscher Transform},

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

url = {https://arxiv.org/pdf/2401.07561},

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 textitquantum 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 = {Tuesday},

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

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

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 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 bivariate bicycle qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast routing with local operations and classical communication (LOCC). Through circuit-level simulations, we find that in some parameter regimes bivariate bicycle codes implemented with this protocol have logical error rates comparable to the surface code while using fewer physical qubits.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_130,

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

author = {Junqiao Lin},

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

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. 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 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 = {Tuesday},

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

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

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. Applying these constructions in various combinations to recent advancements yields near-optimal quantum locally testable codes.},

keywords = {Thursday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_59,

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

author = {Filippo Girardi and Giacomo De Palma},

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

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 = {Friday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_139,

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

author = {Kieran Mastel and William Slofstra},

url = {https://doi.org/10.48550/arXiv.2404.00926},

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 = {Tuesday},

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

url = {https://eprint.iacr.org/2023/410},

year  = {2024},

date = {2024-01-01},

abstract = {Can an adversary compromise the security of our system by obtaining information on sensitive data such as cryptographic keys through side-channels? Even worse, can an adversary hack into our computer and simply steal them? This question is almost as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect such 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, digital signatures and quantum money schemes 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 unbounded number of rounds. - What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack?What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? 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 = {Wednesday},

pubstate = {published},

tppubtype = {Talk}

}

@Talk{T24_316,

title = {Virtual Channel Purification},

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

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

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 = {Tuesday},

pubstate = {published},

tppubtype = {Talk}

}