The Programme Committee of TQC 2024 selected 92 out of 460 submissions for a contributed talk (20% acceptance rate).
You may find the contributed talks here.
The conference schedule is now published.
How to change talk slots: If you are giving a talk and would like to change your scheduled slot, contact the authors of another talk to swap, and write to the organizers only when you have a swap arrangement. You may use the Discord server to ask if anyone is willing to swap. Please try to swap with a talk from the same field, so that sessions can remain thematic and audience members don’t need to move rooms in the middle of a session.
1.
Aleksandrs Belovs
A Direct Reduction from the Polynomial to the Adversary Method Talk
2024.
Abstract | Tags: Monday, Proceedings
@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}
}
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.
2.
Itai Arad, Raz Firanko, Rahul Jain
An area law for the maximally-mixed ground state in arbitrarily degenerate systems with good AGSP Talk
2024.
@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}
}
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.
3.
Eunou Lee, Ojas Parekh
An improved Quantum Max Cut approximation via Maximum Matching Talk
2024.
@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}
}
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
4.
Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, Ojas Parekh
An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut Talk
2024.
@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}
}
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.
5.
Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha
Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
6.
Adam Wills, Min-Hsiu Hsieh, Sergii Strelchuk
Efficient Algorithms for All Port-Based Teleportation Protocols Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
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.
7.
Dmitry Grinko, Adam Burchardt, Maris Ozols
Efficient quantum circuits for port-based teleportation Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
8.
Dominic Berry, Nicholas Rubin, Ahmed Elnabawy, Gabriele Ahlers, Eugene DePrince, Joonho Lee, Christian Gogolin, Ryan Babbush
Efficient Quantum Simulation of Solid-State Materials via Pseudopotentials Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
9.
Robbie King, Kianna Wan, Jarrod McClean
Exponential learning advantages with conjugate states and minimal quantum memory Talk
2024.
@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}
}
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.
10.
Sisi Zhou
Limits of noisy quantum metrology with restricted quantum controls Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
11.
Daniel Stilck França, Cambyse Rouze, Álvaro Alhambra
Making both ends meet: from efficient simulation to universal quantum computing with quantum Gibbs sampling Talk
2024.
@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}
}
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.
12.
Junaid Aftab, Dong An, Konstantina Trivisa
Multi-product Hamiltonian simulation with explicit commutator scaling Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
13.
Joseph Slote
Parity vs. AC0 with simple quantum preprocessing Talk
2024.
@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}
}
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.
14.
Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel, Jordi Weggemans
Permutation tests for quantum state identity Talk
2024.
@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}
}
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.
15.
Joel Rajakumar, James Watson, Yi-Kai Liu
Polynomial-Time Classical Simulation of Noisy IQP Circuits after Constant Depth Talk
2024.
@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}
}
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.
16.
Min-Hsiu Hsieh, Leandro Mendes, Michael Oliveira, Sathyawageeswar Subramanian
Quantum Circuits surpass Biased Threshold Circuits in Constant-Depth Talk
2024.
@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}
}
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.
17.
Jordi Weggemans, Jonas Helsen, Harry Buhrman
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians Talk
2024.
Abstract | Tags: Monday | Links:
@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}
}
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.
18.
Connor Clayton, Yulong Dong, Murphy Yuezhen Niu, Shi Jie Samuel Tan
Signal-Processing Phase Estimation against Time-dependent Errors Talk
2024.
@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}
}
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.
