75 submissions were selected by the Programme Committee to be presented at TQC: 60 talks in the Workshop Track (including 1 merger of 2 submissions) and 14 in the Conference Track, with proceedings.
For now, these are listed in alphabetical order of the title; you can search by author; if an author is listed but no talk is found, they may have an accepted poster.
The Proceedings of the Conference track of TQC 2023 are now published here.
1.
Mark Webster, Armanda Quintavalle, Stephen Bartlett
8 Algorithms for Transversal Diagonal Logical Operators of Stabiliser Codes Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T1119,
title = {8 Algorithms for Transversal Diagonal Logical Operators of Stabiliser Codes},
author = {Mark Webster and Armanda Quintavalle and Stephen Bartlett},
url = {https://arxiv.org/abs/2303.15615},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Storing quantum information in a quantum error correction code can protect it from errors, but the ability to transform the stored quantum information in a fault tolerant way is equally important.
Logical Pauli group operators can be implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category of codes, by applying a series of physical Pauli X and Z gates. Logical operators of this form are fault-tolerant because each qubit is acted upon by at most one gate, limiting the spread of errors, and are referred to as transversal logical operators. Identifying transversal logical operators outside the Pauli group is less well understood. Pauli operators are the first level of the Clifford hierarchy which is deeply connected to fault-tolerance and universality.
In this work, we study transversal logical operators composed of single- and multi-qubit diagonal Clifford hierarchy gates. We demonstrate algorithms for identifying all transversal diagonal logical operators on a CSS code that are more general or have lower computational complexity than previous methods. We also show a method for constructing CSS codes that have a desired diagonal logical Clifford hierarchy operator implemented using single qubit phase gates. Our methods rely on representing operators composed of diagonal Clifford hierarchy gates as diagonal XP operators and this technique may have broader applications.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Storing quantum information in a quantum error correction code can protect it from errors, but the ability to transform the stored quantum information in a fault tolerant way is equally important.
Logical Pauli group operators can be implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category of codes, by applying a series of physical Pauli X and Z gates. Logical operators of this form are fault-tolerant because each qubit is acted upon by at most one gate, limiting the spread of errors, and are referred to as transversal logical operators. Identifying transversal logical operators outside the Pauli group is less well understood. Pauli operators are the first level of the Clifford hierarchy which is deeply connected to fault-tolerance and universality.
In this work, we study transversal logical operators composed of single- and multi-qubit diagonal Clifford hierarchy gates. We demonstrate algorithms for identifying all transversal diagonal logical operators on a CSS code that are more general or have lower computational complexity than previous methods. We also show a method for constructing CSS codes that have a desired diagonal logical Clifford hierarchy operator implemented using single qubit phase gates. Our methods rely on representing operators composed of diagonal Clifford hierarchy gates as diagonal XP operators and this technique may have broader applications.
Logical Pauli group operators can be implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category of codes, by applying a series of physical Pauli X and Z gates. Logical operators of this form are fault-tolerant because each qubit is acted upon by at most one gate, limiting the spread of errors, and are referred to as transversal logical operators. Identifying transversal logical operators outside the Pauli group is less well understood. Pauli operators are the first level of the Clifford hierarchy which is deeply connected to fault-tolerance and universality.
In this work, we study transversal logical operators composed of single- and multi-qubit diagonal Clifford hierarchy gates. We demonstrate algorithms for identifying all transversal diagonal logical operators on a CSS code that are more general or have lower computational complexity than previous methods. We also show a method for constructing CSS codes that have a desired diagonal logical Clifford hierarchy operator implemented using single qubit phase gates. Our methods rely on representing operators composed of diagonal Clifford hierarchy gates as diagonal XP operators and this technique may have broader applications.
2.
Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, Benoît Valiron
A Complete Equational Theory for Quantum Circuits Workshop
2023.
@Workshop{T4856,
title = {A Complete Equational Theory for Quantum Circuits},
author = {Alexandre Clément and Nicolas Heurtel and Shane Mansfield and Simon Perdrix and Benoît Valiron},
year = {2023},
date = {2023-01-01},
abstract = {We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same quantum evolution if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates – that are defined using elementary gates – together with an encoding of quantum circuits into linear optical circuits, for which we introduce a complete axiomatisation. This completeness result lays the formal foundation for the development of compiling tasks like circuit optimisation, hardware constraint satisfaction, and circuit verification.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same quantum evolution if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates – that are defined using elementary gates – together with an encoding of quantum circuits into linear optical circuits, for which we introduce a complete axiomatisation. This completeness result lays the formal foundation for the development of compiling tasks like circuit optimisation, hardware constraint satisfaction, and circuit verification.
3.
Tuomas Laakkonen, Konstantinos Meichanetzidis, John Wetering
A Graphical #SAT Algorithm for Formulae with Small Clause Density Workshop
2023.
@Workshop{T157,
title = {A Graphical #SAT Algorithm for Formulae with Small Clause Density},
author = {Tuomas Laakkonen and Konstantinos Meichanetzidis and John Wetering},
year = {2023},
date = {2023-01-01},
abstract = {We study the counting version of the Boolean satisfiability problem sSAT using the ZH-calculus, a graphical language originally introduced to reason about quantum circuits. Using this we find a natural extension of #SAT which we call #SAT_±, where variables are additionally labelled by phases, which is GapP-complete. Using graphical reasoning, we find a reduction from #SAT to #2SAT_± in the ZH-calculus. We observe that the DPLL algorithm for #2SAT can be adapted to #2SAT_± directly and hence that Wahlstrom's $O^*(1.2377^n)$ upper bound applies to #2SAT_± as well. Combining this with our reduction from #SAT to #2SAT_± gives us novel upper bounds in terms of clauses and variables that are better than $O^*(2^n)$ for small clause densities of $fracmn < 2.25$. This is to our knowledge the first non-trivial upper bound for #SAT that is independent of clause size. Our algorithm improves on Dubois' upper bound for #kSAT whenever $fracmn < 1.85$ and $k geq 4$, and the Williams' average-case analysis whenever $fracmn < 1.21$ and $k geq 6$. We also obtain an upper bound of $O^*(1.1740^L)$ for $sSAT$ in terms of the length of the formula, and find an improved bound on $#textbf3SAT$ for $1.2577 < fracmn łeq frac73$. Our results demonstrate that graphical reasoning can lead to new algorithmic insights, even outside the domain of quantum computing that the calculus was intended for. In addition, using the connection to counting problems, we find a new classical simulation algorithm for quantum computations that runs in $O(1.38^g)$ where g is the number of gates.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
We study the counting version of the Boolean satisfiability problem sSAT using the ZH-calculus, a graphical language originally introduced to reason about quantum circuits. Using this we find a natural extension of #SAT which we call #SAT_±, where variables are additionally labelled by phases, which is GapP-complete. Using graphical reasoning, we find a reduction from #SAT to #2SAT_± in the ZH-calculus. We observe that the DPLL algorithm for #2SAT can be adapted to #2SAT_± directly and hence that Wahlstrom's $O^*(1.2377^n)$ upper bound applies to #2SAT_± as well. Combining this with our reduction from #SAT to #2SAT_± gives us novel upper bounds in terms of clauses and variables that are better than $O^*(2^n)$ for small clause densities of $fracmn < 2.25$. This is to our knowledge the first non-trivial upper bound for #SAT that is independent of clause size. Our algorithm improves on Dubois' upper bound for #kSAT whenever $fracmn < 1.85$ and $k geq 4$, and the Williams' average-case analysis whenever $fracmn < 1.21$ and $k geq 6$. We also obtain an upper bound of $O^*(1.1740^L)$ for $sSAT$ in terms of the length of the formula, and find an improved bound on $#textbf3SAT$ for $1.2577 < fracmn łeq frac73$. Our results demonstrate that graphical reasoning can lead to new algorithmic insights, even outside the domain of quantum computing that the calculus was intended for. In addition, using the connection to counting problems, we find a new classical simulation algorithm for quantum computations that runs in $O(1.38^g)$ where g is the number of gates.
4.
Adrian Chapman, Samuel Elman, Ryan Mann
A Unified Graph-Theoretic Framework for Free-Fermion Solvability Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T6118,
title = {A Unified Graph-Theoretic Framework for Free-Fermion Solvability},
author = {Adrian Chapman and Samuel Elman and Ryan Mann},
url = {https://arxiv.org/pdf/2305.15625.pdf},
year = {2023},
date = {2023-01-01},
abstract = {We show that a quantum spin system has an exact description by noninteracting fermions if its frustration graph is claw-free and contains a simplicial clique. The frustration graph of a spin model captures the pairwise anticommutation relations between Pauli terms of its Hamiltonian in a given basis. This result captures a vast family of known free-fermion solutions. In previous work, it was shown that a free-fermion solution exists if the frustration graph is either a line graph, or (even-hole, claw)-free. The former case generalizes the celebrated Jordan-Wigner transformation and includes the exact solution to the Kitaev honeycomb model. The latter case generalizes a nonlocal solution to the four-fermion model given by Fendley. Our characterization unifies these two approaches, extending generalized Jordan-Wigner solutions to the nonlocal setting and generalizing the four-fermion solution to models of arbitrary spatial dimension. Our key technical insight is the identification of a class of cycle symmetries for all models with claw-free frustration graphs. We prove that these symmetries commute, and this allows us to apply Fendley's solution method to each symmetric subspace independently. Finally, we give a physical description of the fermion modes in terms of operators generated by repeated commutation with the Hamiltonian. This connects our framework to the developing body of work on operator Krylov subspaces. Our results deepen the existing connection between many-body physics and the mathematical theory of claw-free graphs.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
We show that a quantum spin system has an exact description by noninteracting fermions if its frustration graph is claw-free and contains a simplicial clique. The frustration graph of a spin model captures the pairwise anticommutation relations between Pauli terms of its Hamiltonian in a given basis. This result captures a vast family of known free-fermion solutions. In previous work, it was shown that a free-fermion solution exists if the frustration graph is either a line graph, or (even-hole, claw)-free. The former case generalizes the celebrated Jordan-Wigner transformation and includes the exact solution to the Kitaev honeycomb model. The latter case generalizes a nonlocal solution to the four-fermion model given by Fendley. Our characterization unifies these two approaches, extending generalized Jordan-Wigner solutions to the nonlocal setting and generalizing the four-fermion solution to models of arbitrary spatial dimension. Our key technical insight is the identification of a class of cycle symmetries for all models with claw-free frustration graphs. We prove that these symmetries commute, and this allows us to apply Fendley's solution method to each symmetric subspace independently. Finally, we give a physical description of the fermion modes in terms of operators generated by repeated commutation with the Hamiltonian. This connects our framework to the developing body of work on operator Krylov subspaces. Our results deepen the existing connection between many-body physics and the mathematical theory of claw-free graphs.
5.
Ranyiliu Chen, Laura Mančinska, Jurij Volčič
All Projective Measurements Can be Self-tested Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T1712,
title = {All Projective Measurements Can be Self-tested},
author = {Ranyiliu Chen and Laura Mančinska and Jurij Volčič},
url = {https://arxiv.org/abs/2302.00974},
year = {2023},
date = {2023-01-01},
abstract = {We show that every real-valued projective measurement can be self-tested from correlations. To achieve this, we develop the theory of post-hoc self-testing, which extends existing self-tested strategies to incorporate new measurements. A sufficient and computationally feasible condition for a projective measurement to be post-hoc self-tested by a given strategy is proven. Recent work by Mančinska et al. [arXiv:2103.01729] showed that a strategy containing $d+1$ two-output projective measurements and the maximally entangled state with the local dimension d is self-tested. Applying the post-hoc self-testing technique to this work results in an extended strategy that can incorporate any real-valued projective measurement. We further study the general theory of iterative post-hoc self-testing whenever the state in the initial strategy is maximally entangled and characterize the iteratively post-hoc self-tested measurements in terms of a Jordan algebra generated by the initial strategy.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
We show that every real-valued projective measurement can be self-tested from correlations. To achieve this, we develop the theory of post-hoc self-testing, which extends existing self-tested strategies to incorporate new measurements. A sufficient and computationally feasible condition for a projective measurement to be post-hoc self-tested by a given strategy is proven. Recent work by Mančinska et al. [arXiv:2103.01729] showed that a strategy containing $d+1$ two-output projective measurements and the maximally entangled state with the local dimension d is self-tested. Applying the post-hoc self-testing technique to this work results in an extended strategy that can incorporate any real-valued projective measurement. We further study the general theory of iterative post-hoc self-testing whenever the state in the initial strategy is maximally entangled and characterize the iteratively post-hoc self-tested measurements in terms of a Jordan algebra generated by the initial strategy.
6.
Jef Pauwels, Stefano Pironio, Erik Woodhead, Armin Tavakoli
Almost qudits in the prepare-and-measure scenario Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T1960,
title = {Almost qudits in the prepare-and-measure scenario},
author = {Jef Pauwels and Stefano Pironio and Erik Woodhead and Armin Tavakoli},
url = {https://arxiv.org/abs/2208.07887},
year = {2023},
date = {2023-01-01},
abstract = {Quantum communication is often investigated in scenarios where only the dimension of Hilbert space is known. However, assigning a precise dimension is often an approximation of what is actually a higher-dimensional process. Here, we introduce and investigate quantum information encoded in carriers that nearly, but not entirely, correspond to standard qudits. We demonstrate the relevance of this concept for semi-device-independent quantum information by showing how small higher-dimensional components can significantly compromise the conclusions of established protocols. Then we provide a general method, based on semidefinite relaxations, for bounding the set of almost qudit correlations, and apply it to remedy the demonstrated issues. This method also offers a novel systematic approach to the well-known task of device-independent tests of classical and quantum dimensions with unentangled devices. Finally, we also consider viewing almost qubit systems as a physical resource available to the experimenter and determine the optimal quantum protocol for the well-known Random Access Code.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
Quantum communication is often investigated in scenarios where only the dimension of Hilbert space is known. However, assigning a precise dimension is often an approximation of what is actually a higher-dimensional process. Here, we introduce and investigate quantum information encoded in carriers that nearly, but not entirely, correspond to standard qudits. We demonstrate the relevance of this concept for semi-device-independent quantum information by showing how small higher-dimensional components can significantly compromise the conclusions of established protocols. Then we provide a general method, based on semidefinite relaxations, for bounding the set of almost qudit correlations, and apply it to remedy the demonstrated issues. This method also offers a novel systematic approach to the well-known task of device-independent tests of classical and quantum dimensions with unentangled devices. Finally, we also consider viewing almost qubit systems as a physical resource available to the experimenter and determine the optimal quantum protocol for the well-known Random Access Code.
7.
Leonardo Vaglini, Paolo Perinotti, Alessandro Tosini
An operational definition of entropy for post-quantum theories Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T6164,
title = {An operational definition of entropy for post-quantum theories},
author = {Leonardo Vaglini and Paolo Perinotti and Alessandro Tosini},
url = {https://doi.org/10.48550/arXiv.2112.12689 https://doi.org/10.48550/arXiv.2302.01651},
year = {2023},
date = {2023-01-01},
abstract = {The information content of a classical source is defined in terms of the number of bits per symbol that are needed to store the output of the source. An analogous definition is given for a quantum source, where the qubit replaces the bit. Here we show how to extend this definition to operational probabilistic theories. We also discuss some of its properties, such as subadditivity, and to what extent it can be interpreted as a measure of state purity. We also show that none of the proposed generalisations of entropy satisfies a generalised noiseless coding theorem, by means of a toy-theory, consisting of a bilocal version of standard classical theory.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
The information content of a classical source is defined in terms of the number of bits per symbol that are needed to store the output of the source. An analogous definition is given for a quantum source, where the qubit replaces the bit. Here we show how to extend this definition to operational probabilistic theories. We also discuss some of its properties, such as subadditivity, and to what extent it can be interpreted as a measure of state purity. We also show that none of the proposed generalisations of entropy satisfies a generalised noiseless coding theorem, by means of a toy-theory, consisting of a bilocal version of standard classical theory.
8.
Mark Bun, Nadezhda Voronova
Approximate degree lower bounds for oracle identification problems Conference
2023.
Abstract | Tags: Friday | Links:
@Conference{T1116,
title = {Approximate degree lower bounds for oracle identification problems},
author = {Mark Bun and Nadezhda Voronova},
url = {https://arxiv.org/abs/2303.03921 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688780878-poster-1116.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688780878-video-1116.mp4},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function.
We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $latex x ın 0, 1^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $latex x$.
We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $latex Ømega(n/łog^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.},
howpublished = {Talk and Proceedings},
keywords = {Friday},
pubstate = {published},
tppubtype = {Conference}
}
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function.
We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $latex x ın 0, 1^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $latex x$.
We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $latex Ømega(n/łog^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $latex x ın 0, 1^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $latex x$.
We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $latex Ømega(n/łog^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
9.
Arkin Tikku, Isaac Kim
Circuit depth versus energy in topologically ordered systems Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T6087,
title = {Circuit depth versus energy in topologically ordered systems},
author = {Arkin Tikku and Isaac Kim},
url = {https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688308043-poster-6087.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688308043-video-6087.mp4},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most ε with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice Λ, we prove a lower bound of $Ømegałeft(minłeft(1/epsilon^frac1-alpha2, sqrtabsŁambdaright)right)$ for any $alpha >0$. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most ε with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice Λ, we prove a lower bound of $Ømegałeft(minłeft(1/epsilon^frac1-alpha2, sqrtabsŁambdaright)right)$ for any $alpha >0$. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate.
10.
Dominik Wild, Alvaro Alhambra
Classical simulation of short-time quantum dynamics Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T8698,
title = {Classical simulation of short-time quantum dynamics},
author = {Dominik Wild and Alvaro Alhambra},
url = {https://arxiv.org/abs/2210.11490},
year = {2023},
date = {2023-01-01},
abstract = {Recent progress in the development of quantum technologies has enabled the direct investigation of dynamics of increasingly complex quantum many-body systems. This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage. Here we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian. For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error. In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb–Robinson bound. Our results use cluster expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence. This has important physical consequences besides our efficient algorithms. In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
Recent progress in the development of quantum technologies has enabled the direct investigation of dynamics of increasingly complex quantum many-body systems. This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage. Here we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian. For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error. In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb–Robinson bound. Our results use cluster expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence. This has important physical consequences besides our efficient algorithms. In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.
11.
Mirko Arienzo, Markus Heinrich, Ingo Roth, Martin Kliesch
Closed-form analytic expressions for shadow estimation with brickwork circuits Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T7062,
title = {Closed-form analytic expressions for shadow estimation with brickwork circuits},
author = {Mirko Arienzo and Markus Heinrich and Ingo Roth and Martin Kliesch},
url = {https://arxiv.org/abs/2211.09835},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Properties of quantum systems can be estimated using classical shadows, which implement measurements based on random ensembles of unitaries. Originally derived for global Clifford unitaries and products of single-qubit Clifford gates, practical implementations are limited to the latter scheme for moderate numbers of qubits. Beyond local gates, the accurate implementation of very short random circuits with two-local gates is still experimentally feasible and, therefore, interesting for implementing measurements in near-term applications. In this work, we derive closed-form analytical expressions for shadow estimation using brickwork circuits with two layers of parallel two-local Haar-random (or Clifford) unitaries. Besides the construction of the classical shadow, our results give rise to sample-complexity guarantees for estimating Pauli observables. We then compare the performance of shadow estimation with brickwork circuits to the established approach using local Clifford unitaries and find improved sample complexity in the estimation of observables supported on sufficiently many qubits.},
howpublished = {Talk (merged)},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Properties of quantum systems can be estimated using classical shadows, which implement measurements based on random ensembles of unitaries. Originally derived for global Clifford unitaries and products of single-qubit Clifford gates, practical implementations are limited to the latter scheme for moderate numbers of qubits. Beyond local gates, the accurate implementation of very short random circuits with two-local gates is still experimentally feasible and, therefore, interesting for implementing measurements in near-term applications. In this work, we derive closed-form analytical expressions for shadow estimation using brickwork circuits with two layers of parallel two-local Haar-random (or Clifford) unitaries. Besides the construction of the classical shadow, our results give rise to sample-complexity guarantees for estimating Pauli observables. We then compare the performance of shadow estimation with brickwork circuits to the established approach using local Clifford unitaries and find improved sample complexity in the estimation of observables supported on sufficiently many qubits.
12.
Bjarne Bergh, Nilanjana Datta, Robert Salzmann
Composite Classical and Quantum Channel Discrimination Workshop
2023.
@Workshop{T4791,
title = {Composite Classical and Quantum Channel Discrimination},
author = {Bjarne Bergh and Nilanjana Datta and Robert Salzmann},
year = {2023},
date = {2023-01-01},
abstract = {We study the problem of binary composite channel discrimination in the asymmetric setting, where the hypotheses are given by fairly arbitrary sets of channels, and samples do not have to be identically distributed. In the case of quantum channels we prove: (i) a characterization of the Stein's exponent for parallel channel discrimination strategies and (ii) an upper bound on the Stein's exponent for adaptive channel discrimination strategies. We further show that already for classical channels this upper bound can sometimes be achieved and be strictly larger than what is possible with parallel strategies. Hence, there can be an advantage of adaptive channel discrimination strategies with composite hypotheses for classical channels, unlike in the case of simple hypotheses. Moreover, we show that classically this advantage can only exist if the sets of channels corresponding to the hypotheses are non-convex. As a consequence of our more general treatment, which is not limited to the composite i.i.d. setting, we also obtain a generalization of previous composite state discrimination results.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
We study the problem of binary composite channel discrimination in the asymmetric setting, where the hypotheses are given by fairly arbitrary sets of channels, and samples do not have to be identically distributed. In the case of quantum channels we prove: (i) a characterization of the Stein's exponent for parallel channel discrimination strategies and (ii) an upper bound on the Stein's exponent for adaptive channel discrimination strategies. We further show that already for classical channels this upper bound can sometimes be achieved and be strictly larger than what is possible with parallel strategies. Hence, there can be an advantage of adaptive channel discrimination strategies with composite hypotheses for classical channels, unlike in the case of simple hypotheses. Moreover, we show that classically this advantage can only exist if the sets of channels corresponding to the hypotheses are non-convex. As a consequence of our more general treatment, which is not limited to the composite i.i.d. setting, we also obtain a generalization of previous composite state discrimination results.
13.
Alper Cakan, Vipul Goyal, Chen-Da Liu-Zhang, Joao Ribeiro
Computational Quantum Secret Sharing Conference
2023.
Abstract | Tags: Tuesday | Links:
@Conference{T3870,
title = {Computational Quantum Secret Sharing},
author = {Alper Cakan and Vipul Goyal and Chen-Da Liu-Zhang and Joao Ribeiro},
url = {https://arxiv.org/abs/2305.00356},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security).
While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of $n$-party access structures to $1.5^n+o(n)$, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in $mathsfP$ and $mathsfNP$.},
howpublished = {Talk and Proceedings},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Conference}
}
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security).
While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of $n$-party access structures to $1.5^n+o(n)$, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in $mathsfP$ and $mathsfNP$.
While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of $n$-party access structures to $1.5^n+o(n)$, improving upon best known schemes and matching the best known result for general access structures in the classical setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in $mathsfP$ and $mathsfNP$.
14.
Anurag Anshu, Tony Metger
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T4520,
title = {Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations},
author = {Anurag Anshu and Tony Metger},
url = {https://arxiv.org/abs/2209.02715},
year = {2023},
date = {2023-01-01},
abstract = {We prove concentration bounds for the following classes of quantum states:
(i) output states of shallow quantum circuits;
(ii) injective matrix product states;
(iii) output states of dense Hamiltonian evolution, i.e.~states of the form $e^ıota H^(p) cdots e^ıota H^(1) ketpsi_0$ for any $n$-qubit product state $ketpsi_0$, where each $H^(i)$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits.
Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(łog łog n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We prove concentration bounds for the following classes of quantum states:
(i) output states of shallow quantum circuits;
(ii) injective matrix product states;
(iii) output states of dense Hamiltonian evolution, i.e.~states of the form $e^ıota H^(p) cdots e^ıota H^(1) ketpsi_0$ for any $n$-qubit product state $ketpsi_0$, where each $H^(i)$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits.
Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(łog łog n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level.
(i) output states of shallow quantum circuits;
(ii) injective matrix product states;
(iii) output states of dense Hamiltonian evolution, i.e.~states of the form $e^ıota H^(p) cdots e^ıota H^(1) ketpsi_0$ for any $n$-qubit product state $ketpsi_0$, where each $H^(i)$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits.
Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(łog łog n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level.
15.
Matthias Salzger, V. Vilasini
Connecting indefinite causal order processes to composable quantum protocols in a spacetime Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T5276,
title = {Connecting indefinite causal order processes to composable quantum protocols in a spacetime},
author = {Matthias Salzger and V. Vilasini},
url = {https://arxiv.org/abs/2304.06735 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688052738-video-TQC_talk_summary.mp4},
year = {2023},
date = {2023-01-01},
abstract = {The process matrix framework models quantum protocols without assuming a definite acyclic causal order between the operations of parties in the protocol. This leads to so-called indefinite causal order processes which have been shown to provide advantages for quantum information processing. However, there have been longstanding open questions regarding the subset of practically realisable process matrices, as well as challenges in formulating their composition. We make progress on addressing such questions by connecting an important subset of process matrices, namely quantum circuits with quantum control of causal order (QC-QC) with so-called causal boxes which describe practical quantum information protocols in spacetime. Causal boxes are fully closed under composition and incorporate physical principles such as relativistic causality in spacetime. We first identify a notion of operational equivalence between QC-QCs and causal boxes by connecting state spaces and operations in the two formalisms. We then explicitly construct for each QC-QC an operationally equivalent causal box that satisfies certain special mathematical properties that allows the causal box to be interpreted as a process, this corresponds to a subset of causal boxes previously known as process boxes. This allows us to define composition of QC-QCs in terms of composition of causal boxes which is well-defined. We conjecture with a proof sketch that the spatiotemporal labels involved in their description can be simplified to a certain totally ordered form. Based on this, we establish through a constructive proof that every process box can be mapped to an operationally equivalent QCQC. This indicates that the subset of indefinite causal order processes realisable in a background spacetime correspond to controlled superpositions of acyclic orders, which in particular rules out processes violating so-called causal inequalities. Our results shed light on the practicality and composability questions for indefinite causal structures while introducing new physically-motivated tools for studying their applications for quantum information processing in spacetime.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
The process matrix framework models quantum protocols without assuming a definite acyclic causal order between the operations of parties in the protocol. This leads to so-called indefinite causal order processes which have been shown to provide advantages for quantum information processing. However, there have been longstanding open questions regarding the subset of practically realisable process matrices, as well as challenges in formulating their composition. We make progress on addressing such questions by connecting an important subset of process matrices, namely quantum circuits with quantum control of causal order (QC-QC) with so-called causal boxes which describe practical quantum information protocols in spacetime. Causal boxes are fully closed under composition and incorporate physical principles such as relativistic causality in spacetime. We first identify a notion of operational equivalence between QC-QCs and causal boxes by connecting state spaces and operations in the two formalisms. We then explicitly construct for each QC-QC an operationally equivalent causal box that satisfies certain special mathematical properties that allows the causal box to be interpreted as a process, this corresponds to a subset of causal boxes previously known as process boxes. This allows us to define composition of QC-QCs in terms of composition of causal boxes which is well-defined. We conjecture with a proof sketch that the spatiotemporal labels involved in their description can be simplified to a certain totally ordered form. Based on this, we establish through a constructive proof that every process box can be mapped to an operationally equivalent QCQC. This indicates that the subset of indefinite causal order processes realisable in a background spacetime correspond to controlled superpositions of acyclic orders, which in particular rules out processes violating so-called causal inequalities. Our results shed light on the practicality and composability questions for indefinite causal structures while introducing new physically-motivated tools for studying their applications for quantum information processing in spacetime.
16.
Ravi Kunjwal, Victoria Wright
Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T2989,
title = {Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem},
author = {Ravi Kunjwal and Victoria Wright},
url = {https://arxiv.org/abs/2109.13594},
year = {2023},
date = {2023-01-01},
abstract = {The fact that quantum theory radically departs from 'classical lines of thought' is a critical driver for its applications in quantum information and computation. A famous example of this radical departure—this nonclassicality—is entanglement. Bell's theorem shows that shared entanglement can be used to generate correlations between non-communicating parties in ways that are impossible to do without communication if one only had access to classical shared randomness. In their very formulation, both entanglement and Bell's theorem are composite notions of nonclassicality, i.e., they require at least two parties to be meaningful. Another key notion of nonclassicality is contextuality that follows from the Kochen-Specker theorem: this notion is applicable to single systems. I will present some recent results on the interplay between contextuality and entanglement in composite systems and their consequences for our understanding of restricted models of multiqubit quantum computation with state injection that have been previously proposed. Based on V.J. Wright and R. Kunjwal, Quantum 7, 900 (2023).},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
The fact that quantum theory radically departs from 'classical lines of thought' is a critical driver for its applications in quantum information and computation. A famous example of this radical departure—this nonclassicality—is entanglement. Bell's theorem shows that shared entanglement can be used to generate correlations between non-communicating parties in ways that are impossible to do without communication if one only had access to classical shared randomness. In their very formulation, both entanglement and Bell's theorem are composite notions of nonclassicality, i.e., they require at least two parties to be meaningful. Another key notion of nonclassicality is contextuality that follows from the Kochen-Specker theorem: this notion is applicable to single systems. I will present some recent results on the interplay between contextuality and entanglement in composite systems and their consequences for our understanding of restricted models of multiqubit quantum computation with state injection that have been previously proposed. Based on V.J. Wright and R. Kunjwal, Quantum 7, 900 (2023).
17.
Karol Horodecki, Siddhartha Das, Leonard Sikorski, Mark M. Wilde
Cost of quantum secret key Workshop
2023.
Abstract | Tags: Friday | Links:
@workshop{T6076,
title = {Cost of quantum secret key},
author = {Karol Horodecki and Siddhartha Das and Leonard Sikorski and Mark M. Wilde},
url = {https://tqc-conference.org/wp-content/uploads/2023/07/key_cost_q_internet_updated.pdf},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {In this paper, we develop the resource theory of quantum secret key. Operating under the assumption that entangled states with zero distillable key do not exist, we define the key cost of a quantum state, channel, and device. We study its properties through the lens of a quantity that we call the key of formation. The main result of our paper is that the regularized key of formation equals the key cost of a quantum state. The core protocol underlying this result is privacy dilution, which converts states containing ideal privacy into ones with diluted privacy. Additionally, our main result follows by proving that the key of formation is an entanglement monotone with appealing mathematical properties. We further focus on mixed-state analogues of pure quantum states in the domain of privacy, and we prove that a number of entanglement measures are equal to each other for these states, similar to the case of pure entangled states. The privacy cost in the single-shot regime exhibits a yield-cost relation, and basic results for quantum channels and devices are also provided.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {workshop}
}
In this paper, we develop the resource theory of quantum secret key. Operating under the assumption that entangled states with zero distillable key do not exist, we define the key cost of a quantum state, channel, and device. We study its properties through the lens of a quantity that we call the key of formation. The main result of our paper is that the regularized key of formation equals the key cost of a quantum state. The core protocol underlying this result is privacy dilution, which converts states containing ideal privacy into ones with diluted privacy. Additionally, our main result follows by proving that the key of formation is an entanglement monotone with appealing mathematical properties. We further focus on mixed-state analogues of pure quantum states in the domain of privacy, and we prove that a number of entanglement measures are equal to each other for these states, similar to the case of pure entangled states. The privacy cost in the single-shot regime exhibits a yield-cost relation, and basic results for quantum channels and devices are also provided.
18.
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications Workshop
2023.
@Workshop{T4427,
title = {Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications},
author = {François Le Gall and Masayuki Miyamoto and Harumichi Nishimura},
year = {2023},
date = {2023-01-01},
abstract = {The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [QIP 2023] under the term emphstate synthesis. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state $Uketpsi$ at the rightmost node of the line, where $ketpsi$ is a quantum state given at the leftmost node and $U$ is an unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [QIP 2023] under the term emphstate synthesis. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state $Uketpsi$ at the rightmost node of the line, where $ketpsi$ is a quantum state given at the leftmost node and $U$ is an unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.
19.
Chien-Hung Cho, Dominic W. Berry, Min-Hsiu Hsieh
Doubling the order of approximation via the randomized product formula Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T4057,
title = {Doubling the order of approximation via the randomized product formula},
author = {Chien-Hung Cho and Dominic W. Berry and Min-Hsiu Hsieh},
url = {https://arxiv.org/abs/2210.11281},
year = {2023},
date = {2023-01-01},
abstract = {Randomization has been applied to Hamiltonian simulation in a number of ways to improve the accuracy or efficiency of product formulas. Deterministic product formulas are often constructed in a symmetric way to provide accuracy of even order 2k. We show that by applying randomized corrections, it is possible to more than double the order to 4k + 1 (corresponding to a doubling of the order of the error). In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example the Pauli strings as are used in the simulation of quantum chemistry.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
Randomization has been applied to Hamiltonian simulation in a number of ways to improve the accuracy or efficiency of product formulas. Deterministic product formulas are often constructed in a symmetric way to provide accuracy of even order 2k. We show that by applying randomized corrections, it is possible to more than double the order to 4k + 1 (corresponding to a doubling of the order of the error). In practice, applying the corrections in a quantum algorithm requires some structure to the Hamiltonian, for example the Pauli strings as are used in the simulation of quantum chemistry.
20.
Emilio Onorati, Cambyse Rouze, Daniel Stilck Franca, James Watson
Efficient learning of ground & thermal states within phases of matter Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T7940,
title = {Efficient learning of ground & thermal states within phases of matter},
author = {Emilio Onorati and Cambyse Rouze and Daniel Stilck Franca and James Watson},
url = {http://arxiv.org/abs/2301.12946},
year = {2023},
date = {2023-01-01},
abstract = {We consider two related tasks: (a) estimating a parameterisation of a given Gibbs state and expectation values of Lipschitz observables on this state; and (b) learning the expectation values of local observables within a thermal or quantum phase of matter. In both cases, we wish to minimise the number of samples we use to learn these properties to a given precision.
For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable's locality – an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies. For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ−1)) samples – an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average. Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We consider two related tasks: (a) estimating a parameterisation of a given Gibbs state and expectation values of Lipschitz observables on this state; and (b) learning the expectation values of local observables within a thermal or quantum phase of matter. In both cases, we wish to minimise the number of samples we use to learn these properties to a given precision.
For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable's locality – an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies. For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ−1)) samples – an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average. Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.
For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable's locality – an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies. For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ−1)) samples – an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average. Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.
21.
Scott Aaronson, Sabee Grewal
Efficient Tomography of Non-Interacting Fermion States Conference
2023.
@Conference{T8570,
title = {Efficient Tomography of Non-Interacting Fermion States},
author = {Scott Aaronson and Sabee Grewal},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We give an efficient algorithm that learns a non-interacting fermion state, given copies of the state. For a system of $n$ non-interacting fermions and $m$ modes, we show that $O(m^3 n^2 łog(1/delta) / eps^4)$ copies of the input state and $O(m^4 n^2 łog(1/delta)/ eps^4)$ time are sufficient to learn the state to trace distance at most $eps$ with probability at least $1 - delta$. Our algorithm empirically estimates one-mode correlations in $O(m)$ different measurement bases and uses them to reconstruct a succinct description of the entire state efficiently.},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
We give an efficient algorithm that learns a non-interacting fermion state, given copies of the state. For a system of $n$ non-interacting fermions and $m$ modes, we show that $O(m^3 n^2 łog(1/delta) / eps^4)$ copies of the input state and $O(m^4 n^2 łog(1/delta)/ eps^4)$ time are sufficient to learn the state to trace distance at most $eps$ with probability at least $1 - delta$. Our algorithm empirically estimates one-mode correlations in $O(m)$ different measurement bases and uses them to reconstruct a succinct description of the entire state efficiently.
22.
Stephen Piddock, Simon Apers
Elfs, trees and quantum walks Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T5309,
title = {Elfs, trees and quantum walks},
author = {Stephen Piddock and Simon Apers},
url = {https://arxiv.org/abs/2211.16379},
year = {2023},
date = {2023-01-01},
abstract = {We study an elementary Markov process on graphs based on electric flow sampling (elfs). The elfs process repeatedly samples from an electric flow on a graph. While the sinks of the flow are fixed, the source is updated using the electric flow sample, and the process ends when it hits a sink vertex.
We argue that this process naturally connects to many key quantities of interest. E.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights. The initial motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We study an elementary Markov process on graphs based on electric flow sampling (elfs). The elfs process repeatedly samples from an electric flow on a graph. While the sinks of the flow are fixed, the source is updated using the electric flow sample, and the process ends when it hits a sink vertex.
We argue that this process naturally connects to many key quantities of interest. E.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights. The initial motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.
We argue that this process naturally connects to many key quantities of interest. E.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights. The initial motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.
23.
Su-Kuan Chu, Guanyu Zhu, Alexey Gorshkov
Entanglement Renormalization Circuits for Chiral Topological Order Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T7425,
title = {Entanglement Renormalization Circuits for Chiral Topological Order},
author = {Su-Kuan Chu and Guanyu Zhu and Alexey Gorshkov},
url = {https://arxiv.org/abs/2304.13748},
year = {2023},
date = {2023-01-01},
abstract = {Entanglement renormalization circuits are quantum circuits that can be used to prepare large-scale entangled states. For years, it has remained a mystery whether there exist scale-invariant entanglement renormalization circuits for chiral topological order. In this paper, we solve this problem by demonstrating entanglement renormalization circuits for a wide class of chiral topologically ordered states, including a state sharing the same topological properties as Laughlin's bosonic fractional quantum Hall state at filling fraction 1/4 and eight states with Ising-like non-Abelian fusion rules. The key idea is to build entanglement renormalization circuits by interleaving the conventional multi-scale entanglement renormalization ansatz (MERA) circuit (made of spatially local gates) with quasi-local evolution. Given the miraculous power of this circuit to prepare a wide range of chiral topologically ordered states, we refer to these circuits as MERA with quasi-local evolution (MERAQLE).},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Entanglement renormalization circuits are quantum circuits that can be used to prepare large-scale entangled states. For years, it has remained a mystery whether there exist scale-invariant entanglement renormalization circuits for chiral topological order. In this paper, we solve this problem by demonstrating entanglement renormalization circuits for a wide class of chiral topologically ordered states, including a state sharing the same topological properties as Laughlin's bosonic fractional quantum Hall state at filling fraction 1/4 and eight states with Ising-like non-Abelian fusion rules. The key idea is to build entanglement renormalization circuits by interleaving the conventional multi-scale entanglement renormalization ansatz (MERA) circuit (made of spatially local gates) with quasi-local evolution. Given the miraculous power of this circuit to prepare a wide range of chiral topologically ordered states, we refer to these circuits as MERA with quasi-local evolution (MERAQLE).
24.
Aleksander Kubica, Arbel Haim, Yotam Vaknin, Fernando Brandao, Alex Retzker
Erasure qubits Workshop
2023.
@Workshop{T1022,
title = {Erasure qubits},
author = {Aleksander Kubica and Arbel Haim and Yotam Vaknin and Fernando Brandao and Alex Retzker},
year = {2023},
date = {2023-01-01},
abstract = {We address a question of leveraging the noise bias to simplify quantum error correction (QEC) protocols and improve their performance. We focus on the previously unexplored bias between the amplitude damping and dephasing errors that is fundamental to many quantum technologies. We propose a simple scheme to convert amplitude damping errors into erasure errors. Despite its simplicity, our scheme significantly improves the performance of QEC protocols and can be extended to handle leakage errors. Importantly, we provide two concrete realizations with superconducting circuits, analyzing their performance both from the analytical and numerical perspective. Our results provide a breakthrough shift in the current architecture paradigm. Namely, they suggest that engineering efforts should focus on improving the dephasing and the quality of quantum coherent control, as they effectively limit the performance of fault-tolerant protocols.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
We address a question of leveraging the noise bias to simplify quantum error correction (QEC) protocols and improve their performance. We focus on the previously unexplored bias between the amplitude damping and dephasing errors that is fundamental to many quantum technologies. We propose a simple scheme to convert amplitude damping errors into erasure errors. Despite its simplicity, our scheme significantly improves the performance of QEC protocols and can be extended to handle leakage errors. Importantly, we provide two concrete realizations with superconducting circuits, analyzing their performance both from the analytical and numerical perspective. Our results provide a breakthrough shift in the current architecture paradigm. Namely, they suggest that engineering efforts should focus on improving the dephasing and the quality of quantum coherent control, as they effectively limit the performance of fault-tolerant protocols.
25.
Paula Belzig, Matthias Christandl, Alexander Müller-Hermes
Fault-tolerant Coding for Entanglement-Assisted Communication Workshop
2023.
@Workshop{T641,
title = {Fault-tolerant Coding for Entanglement-Assisted Communication},
author = {Paula Belzig and Matthias Christandl and Alexander Müller-Hermes},
year = {2023},
date = {2023-01-01},
abstract = {We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight $k$. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or the particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy, and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight $k$. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or the particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy, and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.
26.
Thomas Wagner, Hermann Kampermann, Dagmar Bruß, Martin Kliesch
Foundations for estimating Pauli noise in quantum error correction Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T1371,
title = {Foundations for estimating Pauli noise in quantum error correction},
author = {Thomas Wagner and Hermann Kampermann and Dagmar Bruß and Martin Kliesch},
url = {https://arxiv.org/abs/2209.09267 https://arxiv.org/abs/2107.14252},
year = {2023},
date = {2023-01-01},
abstract = {The characterization of quantum devices is crucial for their practical implementation but can be costly in experimental effort and classical post-processing. Therefore, it is desirable to measure only information that is relevant for specific applications and develop protocols that require little additional effort. In this work, we focus on the characterization of quantum computers in the context of stabilizer quantum error correction. We prove that (i) physical and (ii) logical error channels induced by Pauli noise can be estimated from syndrome data under minimal conditions. Essentially, any Pauli channel a code can correct can also be estimated from its syndrome measurements. We also provide a concrete estimation algorithm for this task.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
The characterization of quantum devices is crucial for their practical implementation but can be costly in experimental effort and classical post-processing. Therefore, it is desirable to measure only information that is relevant for specific applications and develop protocols that require little additional effort. In this work, we focus on the characterization of quantum computers in the context of stabilizer quantum error correction. We prove that (i) physical and (ii) logical error channels induced by Pauli noise can be estimated from syndrome data under minimal conditions. Essentially, any Pauli channel a code can correct can also be estimated from its syndrome measurements. We also provide a concrete estimation algorithm for this task.
27.
Nishant Rodrigues, Brad Lackey
Fully device-independent quantum key distribution using synchronous correlations Conference
2023.
Abstract | Tags: Wednesday | Links:
@Conference{T6220,
title = {Fully device-independent quantum key distribution using synchronous correlations},
author = {Nishant Rodrigues and Brad Lackey},
url = {https://arxiv.org/abs/2110.14530},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We derive a device-independent quantum key distribution protocol based on synchronous correlations and their Bell inequalities. This protocol offers several advantages over other device-independent schemes including symmetry between the two users and no need for pre-shared randomness. We close a ``synchronicity'' loophole by showing that an almost synchronous correlation inherits the self-testing property of the associated synchronous correlation. We also pose a new security assumption that closes the ``locality'' (or ``causality'') loophole: an unbounded adversary with even a small uncertainty about the users' choice of measurement bases cannot produce any almost synchronous correlation that approximately maximally violates a synchronous Bell inequality.},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
We derive a device-independent quantum key distribution protocol based on synchronous correlations and their Bell inequalities. This protocol offers several advantages over other device-independent schemes including symmetry between the two users and no need for pre-shared randomness. We close a ``synchronicity'' loophole by showing that an almost synchronous correlation inherits the self-testing property of the associated synchronous correlation. We also pose a new security assumption that closes the ``locality'' (or ``causality'') loophole: an unbounded adversary with even a small uncertainty about the users' choice of measurement bases cannot produce any almost synchronous correlation that approximately maximally violates a synchronous Bell inequality.
28.
Pengyu Liu, Zhenhuan Liu, Shu Chen, Xiongfeng Ma
Fundamental Limitation on the Detectability of Entanglement Woekshop
2023.
Abstract | Tags: Tuesday | Links:
@Woekshop{T4375,
title = {Fundamental Limitation on the Detectability of Entanglement},
author = {Pengyu Liu and Zhenhuan Liu and Shu Chen and Xiongfeng Ma},
url = {https://arxiv.org/abs/2208.02518},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Entanglement detection is essential in quantum information science and quantum many-body physics. It has been proved that entanglement exists almost surely for a random quantum state, while the realizations of effective entanglement criteria usually consume exponential resources, and efficient criteria often perform poorly without prior knowledge. This fact implies a fundamental limitation might exist in the detectability of entanglement. In this work, we formalize this limitation as a fundamental trade-off between the efficiency and effectiveness of entanglement criteria via a systematic method to theoretically evaluate the detection capability of entanglement criteria. For a system coupled to an environment, we prove that any entanglement criterion needs exponentially many observables to detect the entanglement effectively when restricted to single-copy operations. Otherwise, the detection capability of the criterion will decay double-exponentially. Furthermore, if multi-copy joint measurements are allowed, the effectiveness of entanglement detection can be exponentially improved, which implies a quantum advantage in entanglement detection problems.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Woekshop}
}
Entanglement detection is essential in quantum information science and quantum many-body physics. It has been proved that entanglement exists almost surely for a random quantum state, while the realizations of effective entanglement criteria usually consume exponential resources, and efficient criteria often perform poorly without prior knowledge. This fact implies a fundamental limitation might exist in the detectability of entanglement. In this work, we formalize this limitation as a fundamental trade-off between the efficiency and effectiveness of entanglement criteria via a systematic method to theoretically evaluate the detection capability of entanglement criteria. For a system coupled to an environment, we prove that any entanglement criterion needs exponentially many observables to detect the entanglement effectively when restricted to single-copy operations. Otherwise, the detection capability of the criterion will decay double-exponentially. Furthermore, if multi-copy joint measurements are allowed, the effectiveness of entanglement detection can be exponentially improved, which implies a quantum advantage in entanglement detection problems.
29.
Di Fang, Yonah Borns-Weil
Going beyond the scale: Uniform observable error bounds for Trotter formulae in the semiclassical regime Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T5924,
title = {Going beyond the scale: Uniform observable error bounds for Trotter formulae in the semiclassical regime},
author = {Di Fang and Yonah Borns-Weil},
url = {https://arxiv.org/abs/2208.07957},
year = {2023},
date = {2023-01-01},
abstract = {By no fast-forwarding theorem, the simulation time for the Hamiltonian evolution needs to be $Ør(|H| t)$, which essentially states that one can not go across the multiple scales as the simulation time for the Hamiltonian evolution needs to be strictly greater than the physical time. We demonstrated in the context of the semiclassical Schrödinger equation that the computational cost for a class of observables can be much lower than the state-of-the-art bounds. In the semiclassical regime (the effective Planck constant $h łl 1$), the operator norm of the Hamiltonian is $Ør(h^-1)$. We show that the number of Trotter steps used for the observable evolution can be $Ør(1)$, that is, to simulate some observables of the Schrödinger equation on a quantum scale only takes the simulation time comparable to the classical scale. In terms of error analysis, we improve the additive observable error bounds [Lasser-Lubich 2020] to uniform-in-$h$ observable error bounds. This is, to our knowledge, the first uniform observable error bound for semiclassical Schr"odinger equation without sacrificing the convergence order of the numerical method. Based on semiclassical calculus and discrete microlocal analysis, our result showcases the potential improvements taking advantage of multiscale properties, such as the smallness of the effective Planck constant, of the underlying dynamics and sheds light on going across the scale for quantum dynamics simulation.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
By no fast-forwarding theorem, the simulation time for the Hamiltonian evolution needs to be $Ør(|H| t)$, which essentially states that one can not go across the multiple scales as the simulation time for the Hamiltonian evolution needs to be strictly greater than the physical time. We demonstrated in the context of the semiclassical Schrödinger equation that the computational cost for a class of observables can be much lower than the state-of-the-art bounds. In the semiclassical regime (the effective Planck constant $h łl 1$), the operator norm of the Hamiltonian is $Ør(h^-1)$. We show that the number of Trotter steps used for the observable evolution can be $Ør(1)$, that is, to simulate some observables of the Schrödinger equation on a quantum scale only takes the simulation time comparable to the classical scale. In terms of error analysis, we improve the additive observable error bounds [Lasser-Lubich 2020] to uniform-in-$h$ observable error bounds. This is, to our knowledge, the first uniform observable error bound for semiclassical Schr"odinger equation without sacrificing the convergence order of the numerical method. Based on semiclassical calculus and discrete microlocal analysis, our result showcases the potential improvements taking advantage of multiscale properties, such as the smallness of the effective Planck constant, of the underlying dynamics and sheds light on going across the scale for quantum dynamics simulation.
30.
Alexander Gresch, Martin Kliesch
Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T8311,
title = {Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping},
author = {Alexander Gresch and Martin Kliesch},
url = {https://arxiv.org/abs/2301.03385},
year = {2023},
date = {2023-01-01},
abstract = {Energy estimation in quantum many-body Hamiltonians is a paradigmatic task in various research fields. In particular, efficient energy estimation may be crucial in achieving a quantum advantage for a practically relevant problem. For instance, the measurement effort poses a crucial bottleneck in variational quantum algorithms. We aim to find the optimal strategy with single-qubit measurements that yields the highest provable accuracy given a total measurement budget. As a central tool, we establish new tail bounds for empirical estimators of the energy. They are useful for identifying measurement settings that improve the energy estimate the most. This task constitutes an NP-hard problem. However, we are able to circumvent this bottleneck and use the tail bounds to develop a practical efficient estimation strategy which we call ShadowGrouping. As the name suggests, it combines shadow estimation methods with grouping strategies for Pauli strings. In numerical experiments, we demonstrate that ShadowGrouping outperforms state-of-the-art methods in estimating the electronic ground-state energies of various small molecules, both in provable and effective accuracy benchmarks. Hence, this work provides a promising way, e.g., to tackle the measurement bottleneck of variational quantum algorithms.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
Energy estimation in quantum many-body Hamiltonians is a paradigmatic task in various research fields. In particular, efficient energy estimation may be crucial in achieving a quantum advantage for a practically relevant problem. For instance, the measurement effort poses a crucial bottleneck in variational quantum algorithms. We aim to find the optimal strategy with single-qubit measurements that yields the highest provable accuracy given a total measurement budget. As a central tool, we establish new tail bounds for empirical estimators of the energy. They are useful for identifying measurement settings that improve the energy estimate the most. This task constitutes an NP-hard problem. However, we are able to circumvent this bottleneck and use the tail bounds to develop a practical efficient estimation strategy which we call ShadowGrouping. As the name suggests, it combines shadow estimation methods with grouping strategies for Pauli strings. In numerical experiments, we demonstrate that ShadowGrouping outperforms state-of-the-art methods in estimating the electronic ground-state energies of various small molecules, both in provable and effective accuracy benchmarks. Hence, this work provides a promising way, e.g., to tackle the measurement bottleneck of variational quantum algorithms.
31.
Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs
Improved Algorithm and Lower Bound for Variable Time Quantum Search Conference
2023.
Abstract | Tags: Friday | Links:
@Conference{T5883,
title = {Improved Algorithm and Lower Bound for Variable Time Quantum Search},
author = {Andris Ambainis and Martins Kokainis and Jevgēnijs Vihrovs},
url = {https://arxiv.org/abs/2302.06749 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688131797-video-video.mp4},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(sqrtTłog n)$ where $T=sum_i=1^n t_i^2$ with $t_i$ denoting the time to check the $i^rm th$ item. Our second result is a quantum lower bound of $Ømega(sqrtTłog T)$. Both the algorithm and the lower bound improve over previously known results by a factor of $sqrtłog T$ but the algorithm is also substantially simpler than the previously known quantum algorithms.},
howpublished = {Talk and Proceedings},
keywords = {Friday},
pubstate = {published},
tppubtype = {Conference}
}
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(sqrtTłog n)$ where $T=sum_i=1^n t_i^2$ with $t_i$ denoting the time to check the $i^rm th$ item. Our second result is a quantum lower bound of $Ømega(sqrtTłog T)$. Both the algorithm and the lower bound improve over previously known results by a factor of $sqrtłog T$ but the algorithm is also substantially simpler than the previously known quantum algorithms.
32.
Daniel Hothem, Ojas Parekh, Kevin Thompson
Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians Conference
2023.
@Conference{T4534,
title = {Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians},
author = {Daniel Hothem and Ojas Parekh and Kevin Thompson},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We give a classical 1/(qk+1)-approximation for the maximum eigenvalue of a k-sparse fermionic Hamiltonian with strictly q-local terms, as well as a 1/(4k+1)-approximation when the Hamiltonian has both 2-local and 4-local terms. More generally, we obtain a 1/O(q*k^2)-approximation for k-sparse fermionic Hamiltonians with terms of locality at most q. Our techniques also yield analogous constant-factor approximations for k-sparse, q-local spin Hamiltonians with small hidden constants and improved dependence on $q$.},
howpublished = {Talk and Proceedings},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Conference}
}
We give a classical 1/(qk+1)-approximation for the maximum eigenvalue of a k-sparse fermionic Hamiltonian with strictly q-local terms, as well as a 1/(4k+1)-approximation when the Hamiltonian has both 2-local and 4-local terms. More generally, we obtain a 1/O(q*k^2)-approximation for k-sparse fermionic Hamiltonians with terms of locality at most q. Our techniques also yield analogous constant-factor approximations for k-sparse, q-local spin Hamiltonians with small hidden constants and improved dependence on $q$.
33.
Francesco Anna Mele, Ludovico Lami, Vittorio Giovannetti
Improved lower bounds on two-way quantum capacities of Gaussian channels Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T5119,
title = {Improved lower bounds on two-way quantum capacities of Gaussian channels},
author = {Francesco Anna Mele and Ludovico Lami and Vittorio Giovannetti},
url = {https://arxiv.org/abs/2303.12867},
year = {2023},
date = {2023-01-01},
abstract = {The two-way capacities of quantum channels determine the ultimate entanglement and secret-key distribution rates achievable by two distant parties that are connected by a noisy transmission line, in absence of quantum repeaters. Since repeaters will likely be expensive to build and maintain, a central open problem of quantum communication is to understand what performances are achievable without them. In this paper, we find a new lower bound on the energy-constrained and unconstrained two-way quantum and secret-key capacities of all phase-insensitive bosonic Gaussian channels, namely thermal attenuator, thermal amplifier, and additive Gaussian noise, which are realistic models for the noise affecting optical fibres or free-space links. Ours is the first nonzero lower bound on the two-way quantum capacity in the parameter range where the (reverse) coherent information becomes negative, and it shows explicitly that entanglement distribution is always possible when the channel is not entanglement breaking. This completely solves a crucial open problem of the field, namely, establishing the maximum excess noise which is tolerable in continuous-variable quantum key distribution. In addition, our construction is fully explicit, i.e.~we devise and optimise a concrete entanglement distribution and distillation protocol that works by combining recurrence and hashing protocols.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
The two-way capacities of quantum channels determine the ultimate entanglement and secret-key distribution rates achievable by two distant parties that are connected by a noisy transmission line, in absence of quantum repeaters. Since repeaters will likely be expensive to build and maintain, a central open problem of quantum communication is to understand what performances are achievable without them. In this paper, we find a new lower bound on the energy-constrained and unconstrained two-way quantum and secret-key capacities of all phase-insensitive bosonic Gaussian channels, namely thermal attenuator, thermal amplifier, and additive Gaussian noise, which are realistic models for the noise affecting optical fibres or free-space links. Ours is the first nonzero lower bound on the two-way quantum capacity in the parameter range where the (reverse) coherent information becomes negative, and it shows explicitly that entanglement distribution is always possible when the channel is not entanglement breaking. This completely solves a crucial open problem of the field, namely, establishing the maximum excess noise which is tolerable in continuous-variable quantum key distribution. In addition, our construction is fully explicit, i.e.~we devise and optimise a concrete entanglement distribution and distillation protocol that works by combining recurrence and hashing protocols.
34.
Thiago Bergamaschi
Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T9627,
title = {Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians},
author = {Thiago Bergamaschi},
url = {https://arxiv.org/abs/2210.08680},
year = {2023},
date = {2023-01-01},
abstract = {The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of textitweak Szemer'edi regularity lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop textitconstant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of textitweak Szemer'edi regularity lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop textitconstant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.
35.
Oliver Reardon-Smith, Kamil Korzekwa, Michał Oszmaniec
Improved simulation of quantum circuits dominated by free Fermionic operations Workshop
2023.
@Workshop{T1889,
title = {Improved simulation of quantum circuits dominated by free Fermionic operations},
author = {Oliver Reardon-Smith and Kamil Korzekwa and Michał Oszmaniec},
year = {2023},
date = {2023-01-01},
abstract = {We present a classical algorithm capable of estimating Born rule probabilities of quantum circuits consisting of matchgate/Fermionic linear optical (FLO) unitaries and non-FLO controlled-phase gates with arbitrary phases. Our algorithm has asymptotic runtime linear in an (in general) exponentially large quantity we have named the “FLO-extent”, and is at most polynomial all other parameters. The FLO-extent is defined in a similar way to the stabilizer extent known from the literature on quantum simulation using stabilizer decompositions. The FLO extent is sub-multiplicative, and the multiplicative upper bound leads to a runtime for our algorithm which doubles for each swap gate, or controlled-Z gate added to the circuit. Controlled-phase gates with different phases have lower extent, smoothly interpolating between 1 and 2. These numbers can be compared with the prior state of-the-art for this task, the runtime of which is multiplied by a factor 9 for each CZ-gate. This dramatic difference in performance is due to our use of methods we have developed to perform tasks in the FLO subtheory in a phase-sensitive way, allowing us to decompose the relevant “magic states” at the level of statevectors rather than density operators. Our results are formulated for quantum circuits, directly extending the class of quantum computations that can be simulated using current classical computers. However, the FLO subtheory also naturally represents the evolution of non-interacting Fermions, while the addition of non-FLO unitaries to the circuit can represent interactions between Fermions. We therefore expect that our results will be applicable to classical simulations of weakly interacting Fermions, with potential applications in condensed matter and quantum chemistry research. In addition to practical simulation our work is part of the ongoing effort to understand the differences between the computational power of classical and that of quantum mechanics. By extending classical simulation methods to new areas we can focus attention on those features of quantum computations which are necessary for meaningful "quantum advantage".},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
We present a classical algorithm capable of estimating Born rule probabilities of quantum circuits consisting of matchgate/Fermionic linear optical (FLO) unitaries and non-FLO controlled-phase gates with arbitrary phases. Our algorithm has asymptotic runtime linear in an (in general) exponentially large quantity we have named the “FLO-extent”, and is at most polynomial all other parameters. The FLO-extent is defined in a similar way to the stabilizer extent known from the literature on quantum simulation using stabilizer decompositions. The FLO extent is sub-multiplicative, and the multiplicative upper bound leads to a runtime for our algorithm which doubles for each swap gate, or controlled-Z gate added to the circuit. Controlled-phase gates with different phases have lower extent, smoothly interpolating between 1 and 2. These numbers can be compared with the prior state of-the-art for this task, the runtime of which is multiplied by a factor 9 for each CZ-gate. This dramatic difference in performance is due to our use of methods we have developed to perform tasks in the FLO subtheory in a phase-sensitive way, allowing us to decompose the relevant “magic states” at the level of statevectors rather than density operators. Our results are formulated for quantum circuits, directly extending the class of quantum computations that can be simulated using current classical computers. However, the FLO subtheory also naturally represents the evolution of non-interacting Fermions, while the addition of non-FLO unitaries to the circuit can represent interactions between Fermions. We therefore expect that our results will be applicable to classical simulations of weakly interacting Fermions, with potential applications in condensed matter and quantum chemistry research. In addition to practical simulation our work is part of the ongoing effort to understand the differences between the computational power of classical and that of quantum mechanics. By extending classical simulation methods to new areas we can focus attention on those features of quantum computations which are necessary for meaningful "quantum advantage".
36.
Francisco Escudero Gutiérrez
Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T5976,
title = {Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms},
author = {Francisco Escudero Gutiérrez},
url = {https://arxiv.org/abs/2304.06713},
year = {2023},
date = {2023-01-01},
abstract = {We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.
We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials.This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]^2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.
37.
Nolan Coble, Matthew Coudron, Jon Nelson, Seyed Sajjad Nezhadi
Local Hamiltonians with no low-energy stabilizer states Conference
2023.
Abstract | Tags: Friday | Links:
@Conference{T9486,
title = {Local Hamiltonians with no low-energy stabilizer states},
author = {Nolan Coble and Matthew Coudron and Jon Nelson and Seyed Sajjad Nezhadi},
url = {https://arxiv.org/abs/2302.14755},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228},
howpublished = {Talk and Proceedings},
keywords = {Friday},
pubstate = {published},
tppubtype = {Conference}
}
The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228
[GL22] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transfor- mation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. doi:10.1145/3519935.3519991 [ABN22] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes, Jun 2022. arXiv:2206.13228
38.
Roberto Rubboli, Marco Tomamichel
New additivity properties of the relative entropy of entanglement and its generalizations Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T7681,
title = {New additivity properties of the relative entropy of entanglement and its generalizations},
author = {Roberto Rubboli and Marco Tomamichel},
url = {https://arxiv.org/abs/2211.12804},
year = {2023},
date = {2023-01-01},
abstract = {We prove that the relative entropy of entanglement is additive when at least one of the two states belongs to some specific class. We show that these classes include bipartite pure, maximally correlated, GHZ, Bell diagonal, isotropic, and generalized Dicke states. Previously, additivity was established only if both states belong to the same class. Moreover, we extend these results to entanglement monotones based on the α-$z$ Rényi relative entropy. Notably, this family of monotones includes also the generalized robustness of entanglement and the geometric measure of entanglement. In addition, we prove that any monotone based on a quantum relative entropy is not additive for general states.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
We prove that the relative entropy of entanglement is additive when at least one of the two states belongs to some specific class. We show that these classes include bipartite pure, maximally correlated, GHZ, Bell diagonal, isotropic, and generalized Dicke states. Previously, additivity was established only if both states belong to the same class. Moreover, we extend these results to entanglement monotones based on the α-$z$ Rényi relative entropy. Notably, this family of monotones includes also the generalized robustness of entanglement and the geometric measure of entanglement. In addition, we prove that any monotone based on a quantum relative entropy is not additive for general states.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.
We also compute closed-form expressions of the monotones for bipartite pure, Bell diagonal, isotropic, generalized Werner, generalized Dicke, and maximally correlated Bell diagonal states. Our results rely on proving new necessary and sufficient conditions for the optimizer of the monotones based on the α-$z$ R'enyi relative entropy, which allow us to reduce the original optimization problem to a simpler linear one. Even though we focus mostly on entanglement theory, we formulate some of our technical results in a general resource theory framework, and we expect that they could be used to investigate other resource theories.
39.
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner
On the complexity of hybrid quantum computation Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T9686,
title = {On the complexity of hybrid quantum computation},
author = {Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner},
url = {https://arxiv.org/abs/2210.06454 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688218994-poster-9686.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688218994-video-9686.mp4},
year = {2023},
date = {2023-01-01},
abstract = {We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle:
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle:
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.
(a) $latex mathsfBPP^QNC^BPP neq mathsfBQP$. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing.
(b) $latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC$ and $latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP$ This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22].
[Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.
40.
Eric Chitambar, Felix Leditzky
On the Duality of Teleportation and Dense Coding Workshop
2023.
@Workshop{T2414,
title = {On the Duality of Teleportation and Dense Coding},
author = {Eric Chitambar and Felix Leditzky},
year = {2023},
date = {2023-01-01},
abstract = {Quantum teleportation is a quantum communication primitive that allows a long-distance quantum channel to be built using pre-shared entanglement and one-way classical communication. However, the quality of the established channel crucially depends on the quality of the pre-shared entanglement. In this work, we revisit the problem of using noisy entanglement for the task of teleportation. We first show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. This also yields a new proof of the known fact that bound entangled states cannot exceed the classical teleportation threshold. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. We also discuss the duality from a communication capacity point of view, deriving upper and lower bounds on the accessible information of a dense coding protocol in terms of the fidelity of its associated teleportation protocol. A corollary of this discussion is a simple proof of the previously established fact that bound entangled states do not provide any advantage in dense coding.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
Quantum teleportation is a quantum communication primitive that allows a long-distance quantum channel to be built using pre-shared entanglement and one-way classical communication. However, the quality of the established channel crucially depends on the quality of the pre-shared entanglement. In this work, we revisit the problem of using noisy entanglement for the task of teleportation. We first show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. This also yields a new proof of the known fact that bound entangled states cannot exceed the classical teleportation threshold. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. We also discuss the duality from a communication capacity point of view, deriving upper and lower bounds on the accessible information of a dense coding protocol in terms of the fidelity of its associated teleportation protocol. A corollary of this discussion is a simple proof of the previously established fact that bound entangled states do not provide any advantage in dense coding.
41.
Marcel Dall'Agnol, Nicholas Spooner
On the Necessity of Collapsing for Post-Quantum and Quantum Commitments Conference
2023.
Abstract | Tags: Wednesday | Links:
@Conference{T2208,
title = {On the Necessity of Collapsing for Post-Quantum and Quantum Commitments},
author = {Marcel Dall'Agnol and Nicholas Spooner},
url = {https://eprint.iacr.org/2022/786 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688327217-video-Talk.mp4},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Collapse binding and collapsing were proposed as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the ""lifting"" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
Collapse binding and collapsing were proposed as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the ""lifting"" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of ""weak"" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a ""win-win"" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives).
42.
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
On the power of nonstandard quantum oracles Conference
2023.
Abstract | Tags: Friday | Links:
@Conference{T7817,
title = {On the power of nonstandard quantum oracles},
author = {Roozbeh Bassirian and Bill Fefferman and Kunal Marwaha},
url = {https://arxiv.org/abs/2212.00098},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.},
howpublished = {Talk and Proceedings},
keywords = {Friday},
pubstate = {published},
tppubtype = {Conference}
}
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.
43.
Ke Li, Yongsheng Yao
Operational Interpretation of the Sandwiched Renyi Divergence of Order 1/2 to 1 as Strong Converse Exponents Workshop
2023.
@Workshop{T8411,
title = {Operational Interpretation of the Sandwiched Renyi Divergence of Order 1/2 to 1 as Strong Converse Exponents},
author = {Ke Li and Yongsheng Yao},
year = {2023},
date = {2023-01-01},
abstract = {We provide the sandwiched Renyi divergence of order $alphaın(1/2,1)$, as well as its induced quantum information quantities, with an operational interpretation in the characterization of the exact strong converse exponents of quantum tasks. Specifically, we consider (a) smoothing of the max-relative entropy, (b) quantum privacy amplification, and (c) quantum information decoupling. We solve the problem of determining the exact strong converse exponents for these three tasks, with the performance being measured by the fidelity or purified distance. The results are given in terms of the sandwiched Renyi divergence of order $alphaın(1/2,1)$, and its induced quantum Renyi conditional entropy and quantum Renyi mutual information. This is the first time to find the precise operational meaning for the sandwiched Renyi divergence with Renyi parameter in the interval $alphaın(1/2,1)$.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
We provide the sandwiched Renyi divergence of order $alphaın(1/2,1)$, as well as its induced quantum information quantities, with an operational interpretation in the characterization of the exact strong converse exponents of quantum tasks. Specifically, we consider (a) smoothing of the max-relative entropy, (b) quantum privacy amplification, and (c) quantum information decoupling. We solve the problem of determining the exact strong converse exponents for these three tasks, with the performance being measured by the fidelity or purified distance. The results are given in terms of the sandwiched Renyi divergence of order $alphaın(1/2,1)$, and its induced quantum Renyi conditional entropy and quantum Renyi mutual information. This is the first time to find the precise operational meaning for the sandwiched Renyi divergence with Renyi parameter in the interval $alphaın(1/2,1)$.
44.
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, Theodore Yoder
Optimal algorithms for learning quantum phase states Conference
2023.
@Conference{T2296,
title = {Optimal algorithms for learning quantum phase states},
author = {Srinivasan Arunachalam and Sergey Bravyi and Arkopal Dutt and Theodore Yoder},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Collapse binding and collapsing were proposed by Unruh (Eurocrypt ’16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the “lifting” of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of “weak” binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a “win-win” result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt ’19) showing that the same object yields quantum lightning.},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
Collapse binding and collapsing were proposed by Unruh (Eurocrypt ’16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the “lifting” of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of “weak” binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a “win-win” result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt ’19) showing that the same object yields quantum lightning.
In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-and-open protocol communicates quantum information.
As a consequence, we establish that a variety of “weak” binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a “win-win” result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt ’19) showing that the same object yields quantum lightning.
45.
Vivien Vandaele, Simon Martiel, Simon Perdrix, Christophe Vuillot
Optimal Hadamard gate count for Clifford+T synthesis of Pauli rotations sequences Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T4442,
title = {Optimal Hadamard gate count for Clifford+T synthesis of Pauli rotations sequences},
author = {Vivien Vandaele and Simon Martiel and Simon Perdrix and Christophe Vuillot},
url = {https://arxiv.org/abs/2302.07040},
year = {2023},
date = {2023-01-01},
abstract = {The Clifford+T gate set is commonly used to perform universal quantum computation. In such setup the T gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of T gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial T-count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of T gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last T gate of the circuit.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
The Clifford+T gate set is commonly used to perform universal quantum computation. In such setup the T gate is typically much more expensive to implement in a fault-tolerant way than Clifford gates. To improve the feasibility of fault-tolerant quantum computing it is then crucial to minimize the number of T gates. Many algorithms, yielding effective results, have been designed to address this problem. It has been demonstrated that performing a pre-processing step consisting of reducing the number of Hadamard gates in the circuit can help to exploit the full potential of these algorithms and thereby lead to a substantial T-count reduction. Moreover, minimizing the number of Hadamard gates also restrains the number of additional qubits and operations resulting from the gadgetization of Hadamard gates, a procedure used by some compilers to further reduce the number of T gates. In this work we tackle the Hadamard gate reduction problem, and propose an algorithm for synthesizing a sequence of Pauli rotations with a minimal number of Hadamard gates. Based on this result, we present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last T gate of the circuit.
46.
Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha
Optimal lower bounds for Quantum Learning via Information Theory Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T6592,
title = {Optimal lower bounds for Quantum Learning via Information Theory},
author = {Shima Bab Hadiashar and Ashwin Nayak and Pulkit Sinha},
url = {https://arxiv.org/abs/2301.02227 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688206526-poster-TQC2023_prerec.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688206526-video-TQC_final_prerec.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, Arunachalam and de Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. They established lower bounds on sample complexity via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both the PAC and agnostic models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC, 2020) characterized the quantum sample complexity of this problem up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, while the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharp lower bound for the Quantum Coupon Collector problem, with the exact leading order term, via the generalized Holevo-Curlander bounds on the distinguishability of an ensemble. All the aspects of the Quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, Arunachalam and de Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. They established lower bounds on sample complexity via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both the PAC and agnostic models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC, 2020) characterized the quantum sample complexity of this problem up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, while the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharp lower bound for the Quantum Coupon Collector problem, with the exact leading order term, via the generalized Holevo-Curlander bounds on the distinguishability of an ensemble. All the aspects of the Quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest.
47.
Qiushi Liu, Zihao Hu, Haidong Yuan, Yuxiang Yang
Optimal Strategies of Quantum Metrology with a Strict Hierarchy Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T6695,
title = {Optimal Strategies of Quantum Metrology with a Strict Hierarchy},
author = {Qiushi Liu and Zihao Hu and Haidong Yuan and Yuxiang Yang},
url = {https://arxiv.org/abs/2203.09758},
year = {2023},
date = {2023-01-01},
abstract = {One of the main quests in quantum metrology is to attain the ultimate precision limit with given resources, where the resources are not only of the number of queries, but more importantly of the allowed strategies. With the same number of queries, the restrictions on the strategies constrain the achievable precision. In this work, we establish a systematic framework to identify the ultimate precision limit of different families of strategies, including the parallel, the sequential, and the indefinite-causal-order strategies, and provide an efficient algorithm that determines an optimal strategy within the family of strategies under consideration. With our framework, we show there exists a strict hierarchy of the precision limits for different families of strategies.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
One of the main quests in quantum metrology is to attain the ultimate precision limit with given resources, where the resources are not only of the number of queries, but more importantly of the allowed strategies. With the same number of queries, the restrictions on the strategies constrain the achievable precision. In this work, we establish a systematic framework to identify the ultimate precision limit of different families of strategies, including the parallel, the sequential, and the indefinite-causal-order strategies, and provide an efficient algorithm that determines an optimal strategy within the family of strategies under consideration. With our framework, we show there exists a strict hierarchy of the precision limits for different families of strategies.
48.
Joel Klassen, Riley Chien
Optimizing Fermionic Encodings for both Hamiltonian and Hardware Workshop
2023.
@Workshop{T7353,
title = {Optimizing Fermionic Encodings for both Hamiltonian and Hardware},
author = {Joel Klassen and Riley Chien},
year = {2023},
date = {2023-01-01},
abstract = {In this work we present a method for generating a fermionic encoding tailored to a set of target fermionic operators and to a target hardware connectivity. Our method uses brute force search, over the space of all encodings which map from Majorana monomials to Pauli operators, to find an encoding which optimizes a target cost function. In contrast to earlier works in this direction, our method searches over an extremely broad class of encodings which subsumes all known second quantized encodings that constitute algebra homomorphisms. In order to search over this class, we give a clear mathematical explanation of how precisely it is characterized, and how to translate this characterization into constructive search criteria. A benefit of searching over this class is that our method is able to supply fairly general optimality guarantees on solutions. A second benefit is that our method is, in principal, capable of finding more efficient representations of fermionic systems when the set of fermionic operators under consideration are faithfully represented by a smaller quotient algebra. Given the high algorithmic cost of performing the search, we adapt our method to handle translationally invariant systems that can be described by a small unit cell that is less costly. We demonstrate our method on various pairings of target fermionic operators and hardware connectivities. We additionally show how our method can be extended to find error detecting fermionic encodings in this class.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
In this work we present a method for generating a fermionic encoding tailored to a set of target fermionic operators and to a target hardware connectivity. Our method uses brute force search, over the space of all encodings which map from Majorana monomials to Pauli operators, to find an encoding which optimizes a target cost function. In contrast to earlier works in this direction, our method searches over an extremely broad class of encodings which subsumes all known second quantized encodings that constitute algebra homomorphisms. In order to search over this class, we give a clear mathematical explanation of how precisely it is characterized, and how to translate this characterization into constructive search criteria. A benefit of searching over this class is that our method is able to supply fairly general optimality guarantees on solutions. A second benefit is that our method is, in principal, capable of finding more efficient representations of fermionic systems when the set of fermionic operators under consideration are faithfully represented by a smaller quotient algebra. Given the high algorithmic cost of performing the search, we adapt our method to handle translationally invariant systems that can be described by a small unit cell that is less costly. We demonstrate our method on various pairings of target fermionic operators and hardware connectivities. We additionally show how our method can be extended to find error detecting fermionic encodings in this class.
49.
Matthias C. Caro, Hsin-Yuan Huang, Joe Gibbs, Nic Ezzell, Andrew Sornborger, Lukasz Cincio, Patrick Coles, Zoe Holmes
Out-of-distribution generalization for learning quantum dynamics and dynamical simulation Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T2904,
title = {Out-of-distribution generalization for learning quantum dynamics and dynamical simulation},
author = {Matthias C. Caro and Hsin-Yuan Huang and Joe Gibbs and Nic Ezzell and Andrew Sornborger and Lukasz Cincio and Patrick Coles and Zoe Holmes},
url = {https://arxiv.org/abs/2204.10268 https://arxiv.org/abs/2204.10269 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1687637585-poster-2904.pdf https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1687637585-video-2904.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Generalization bounds are a critical tool to assess the training data requirements of Quantum Machine Learning (QML). In this work, we prove the first out-of-distribution generalization guarantees in QML, where we require a trained model to perform well even on testing data drawn from a distribution different from the training data distribution. Namely, we establish out-of-distribution generalization for the task of learning an unknown unitary using a quantum neural network and for a broad class of training and testing distributions. In particular, we show that one can learn the action of a unitary on entangled states using only product state training data. Since product states can be prepared using only single-qubit gates, this advances the near-term prospects of QML for learning quantum dynamics, and further opens up new methods for both the classical and quantum compilation of quantum circuits. Based on these insights, we propose a QML-based algorithm for simulating quantum dynamics on near-term quantum hardware and rigorously prove its resource-efficiency in terms of qubit and training data requirements. We also demonstrate the viability of this algorithm through numerical experiments, both in classical simulations and on quantum hardware. Finally, we embed this algorithm in a broader framework for using QML methods for quantum dynamical simulation on NISQ devices.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
Generalization bounds are a critical tool to assess the training data requirements of Quantum Machine Learning (QML). In this work, we prove the first out-of-distribution generalization guarantees in QML, where we require a trained model to perform well even on testing data drawn from a distribution different from the training data distribution. Namely, we establish out-of-distribution generalization for the task of learning an unknown unitary using a quantum neural network and for a broad class of training and testing distributions. In particular, we show that one can learn the action of a unitary on entangled states using only product state training data. Since product states can be prepared using only single-qubit gates, this advances the near-term prospects of QML for learning quantum dynamics, and further opens up new methods for both the classical and quantum compilation of quantum circuits. Based on these insights, we propose a QML-based algorithm for simulating quantum dynamics on near-term quantum hardware and rigorously prove its resource-efficiency in terms of qubit and training data requirements. We also demonstrate the viability of this algorithm through numerical experiments, both in classical simulations and on quantum hardware. Finally, we embed this algorithm in a broader framework for using QML methods for quantum dynamical simulation on NISQ devices.
50.
Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, Earl T. Campbell
Parallel window decoding enables scalable fault tolerant quantum computation Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T8982,
title = {Parallel window decoding enables scalable fault tolerant quantum computation},
author = {Luka Skoric and Dan E. Browne and Kenton M. Barnes and Neil I. Gillespie and Earl T. Campbell},
url = {https://arxiv.org/abs/2209.08552},
year = {2023},
date = {2023-01-01},
abstract = {Large-scale quantum computers have the potential to hold computational capabilities beyond conventional computers for certain problems. However, the physical qubits within a quantum computer are prone to noise and decoherence, which must be corrected in order to perform reliable, fault-tolerant quantum computations. Quantum Error Correction (QEC) provides the path for realizing such computations. QEC continuously generates a continuous stream of data that decoders must process at the rate it is received, which can be as fast as 1 MHz in superconducting quantum computers. A little known fact of QEC is that if the decoder infrastructure cannot keep up, a data backlog problem is encountered and the quantum computer runs exponentially slower. Today's leading approaches to quantum error correction are not scalable as existing decoders typically run slower as the problem size is increased, inevitably hitting the backlog problem. That is: the current leading proposal for fault-tolerant quantum computation is not scalable. Here, we show how to parallelize decoding to achieve almost arbitrary speed, removing this roadblock to scalability. Our parallelization requires some classical feed forward decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now only polynomial in code size, averting the exponential slowdown. We numerically demonstrate our parallel decoder for the surface code, showing no noticeable reduction in logical fidelity compared to previous decoders and demonstrating the parallelization speedup.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Large-scale quantum computers have the potential to hold computational capabilities beyond conventional computers for certain problems. However, the physical qubits within a quantum computer are prone to noise and decoherence, which must be corrected in order to perform reliable, fault-tolerant quantum computations. Quantum Error Correction (QEC) provides the path for realizing such computations. QEC continuously generates a continuous stream of data that decoders must process at the rate it is received, which can be as fast as 1 MHz in superconducting quantum computers. A little known fact of QEC is that if the decoder infrastructure cannot keep up, a data backlog problem is encountered and the quantum computer runs exponentially slower. Today's leading approaches to quantum error correction are not scalable as existing decoders typically run slower as the problem size is increased, inevitably hitting the backlog problem. That is: the current leading proposal for fault-tolerant quantum computation is not scalable. Here, we show how to parallelize decoding to achieve almost arbitrary speed, removing this roadblock to scalability. Our parallelization requires some classical feed forward decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now only polynomial in code size, averting the exponential slowdown. We numerically demonstrate our parallel decoder for the surface code, showing no noticeable reduction in logical fidelity compared to previous decoders and demonstrating the parallelization speedup.
51.
Michael Bremner, Zhengfeng Ji, Xingjian Li, Luke Mathieson, Mauro Morales
Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T600,
title = {Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis},
author = {Michael Bremner and Zhengfeng Ji and Xingjian Li and Luke Mathieson and Mauro Morales},
url = {http://arxiv.org/abs/2211.05325},
year = {2023},
date = {2023-01-01},
abstract = {We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight $latex k$. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed-parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight $latex k$. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed-parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.
52.
Joao Basso, David Gamarnik, Song Mei, Leo Zhou
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T1002,
title = {Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models},
author = {Joao Basso and David Gamarnik and Song Mei and Leo Zhou},
url = {https://arxiv.org/abs/2204.10306},
year = {2023},
date = {2023-01-01},
abstract = {The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when q >= 4 and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when q >= 4 and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.
53.
Jinzhao Sun, Suguru Endo, Patrick Hayden, Huiping Lin, Xiao Yuan, Vlatko Vedral
Perturbative quantum simulation Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T3955,
title = {Perturbative quantum simulation},
author = {Jinzhao Sun and Suguru Endo and Patrick Hayden and Huiping Lin and Xiao Yuan and Vlatko Vedral},
url = {https://arxiv.org/abs/2106.05938},
year = {2023},
date = {2023-01-01},
abstract = {Approximation based on perturbation theory is the foundation for most of the quantitative predictions of quantum mechanics, whether in quantum many-body physics, chemistry, or other domains. Quantum computing provides an alternative to the perturbation paradigm, yet current quantum processors with few noisy qubits are of limited practical utility. In this talk, we introduce perturbative quantum simulation, which combines the complementary strengths of the two approaches, enabling the solution of large quantum problems using limited intermediate-scale quantum hardware. The use of a quantum processor alleviates the need to identify a solvable unperturbed Hamiltonian, while the introduction of perturbative coupling permits a quantum processor to simulate systems with larger sizes. We present an explicit perturbative expansion that mimics the Dyson series expansion and involves only local unitary operations. We then discuss its optimality over other expansions under certain conditions. This perturbative approach is benchmarked by simulating the interacting dynamics of representative quantum systems.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
Approximation based on perturbation theory is the foundation for most of the quantitative predictions of quantum mechanics, whether in quantum many-body physics, chemistry, or other domains. Quantum computing provides an alternative to the perturbation paradigm, yet current quantum processors with few noisy qubits are of limited practical utility. In this talk, we introduce perturbative quantum simulation, which combines the complementary strengths of the two approaches, enabling the solution of large quantum problems using limited intermediate-scale quantum hardware. The use of a quantum processor alleviates the need to identify a solvable unperturbed Hamiltonian, while the introduction of perturbative coupling permits a quantum processor to simulate systems with larger sizes. We present an explicit perturbative expansion that mimics the Dyson series expansion and involves only local unitary operations. We then discuss its optimality over other expansions under certain conditions. This perturbative approach is benchmarked by simulating the interacting dynamics of representative quantum systems.
54.
Stacey Jeffery, Shelby Kimmel, Alvaro Piedrafita
Quantum Algorithm for Path-Edge Sampling Conference
2023.
@Conference{T4248,
title = {Quantum Algorithm for Path-Edge Sampling},
author = {Stacey Jeffery and Shelby Kimmel and Alvaro Piedrafita},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We present a quantum algorithm for sampling an edge on a path between two nodes $s$ and $t$ in a graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between $s$ and $t$. We use this path sampling algorithm as a subroutine for $st$-path finding and $st$-cut finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.},
howpublished = {Talk and Proceedings},
keywords = {Friday},
pubstate = {published},
tppubtype = {Conference}
}
We present a quantum algorithm for sampling an edge on a path between two nodes $s$ and $t$ in a graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between $s$ and $t$. We use this path sampling algorithm as a subroutine for $st$-path finding and $st$-cut finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.
55.
Andrew Childs, Matthew Coudron, Amin Shiraz Gilani
Quantum algorithms and the power of forgetting Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T1025,
title = {Quantum algorithms and the power of forgetting},
author = {Andrew Childs and Matthew Coudron and Amin Shiraz Gilani},
url = {https://arxiv.org/abs/2211.12447},
year = {2023},
date = {2023-01-01},
abstract = {The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.
56.
William Kretschmer
Quantum Mass Production Theorems Conference
2023.
Abstract | Tags: Wednesday | Links:
@Conference{T6465,
title = {Quantum Mass Production Theorems},
author = {William Kretschmer},
url = {https://arxiv.org/abs/2212.14399},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We prove that for any $n$-qubit unitary transformation $U$ and for any $r = 2^o(n / łog n)$, there exists a quantum circuit to implement $U^øtimes r$ with at most $O(4^n)$ gates. This asymptotically equals the number of gates needed to implement just a single copy of a worst-case $U$. We also establish analogous results for quantum states and diagonal unitary transformations. Our techniques are based on the work of Uhlig [Math. Notes 1974], who proved a similar mass production theorem for Boolean functions.},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
We prove that for any $n$-qubit unitary transformation $U$ and for any $r = 2^o(n / łog n)$, there exists a quantum circuit to implement $U^øtimes r$ with at most $O(4^n)$ gates. This asymptotically equals the number of gates needed to implement just a single copy of a worst-case $U$. We also establish analogous results for quantum states and diagonal unitary transformations. Our techniques are based on the work of Uhlig [Math. Notes 1974], who proved a similar mass production theorem for Boolean functions.
57.
Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, Vedran Dunjko
Quantum policy gradient algorithms Conference
2023.
Abstract | Tags: Wednesday | Links:
@Conference{T8953,
title = {Quantum policy gradient algorithms},
author = {Sofiene Jerbi and Arjan Cornelissen and Maris Ozols and Vedran Dunjko},
url = {https://arxiv.org/abs/2212.09328},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.},
howpublished = {Talk and Proceedings},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Conference}
}
Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.
58.
David Trillo, Thinh Le, Miguel Navascues
Quantum supremacy in mechanical tasks: projectiles, rockets and quantum backflow Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T5145,
title = {Quantum supremacy in mechanical tasks: projectiles, rockets and quantum backflow},
author = {David Trillo and Thinh Le and Miguel Navascues},
url = {https://arxiv.org/abs/2209.00725},
year = {2023},
date = {2023-01-01},
abstract = {We consider a non-relativistic quantum particle in an infinite line. We estimate the maximum probability of finding the particle at some distant position given that it is initially bound in some region. We prove that quantum mechanics allows for greater probabilities than classical mechanics - thus obtaining a new kind of quantum advantage. We show that this effect is mathematically related to quantum backflow, and use this to improve the upper bounds on the Bracken-Mellow constant. Several generalizations are studied.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
We consider a non-relativistic quantum particle in an infinite line. We estimate the maximum probability of finding the particle at some distant position given that it is initially bound in some region. We prove that quantum mechanics allows for greater probabilities than classical mechanics - thus obtaining a new kind of quantum advantage. We show that this effect is mathematically related to quantum backflow, and use this to improve the upper bounds on the Bracken-Mellow constant. Several generalizations are studied.
59.
Marco Fanizza, Josep Lumbreras, Andreas Winter
Quantum theory in finite dimension cannot explain every general process with finite memory Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T4004,
title = {Quantum theory in finite dimension cannot explain every general process with finite memory},
author = {Marco Fanizza and Josep Lumbreras and Andreas Winter},
url = {https://arxiv.org/abs/2209.11225 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688151704-video-4004tqc2023.mp4},
year = {2023},
date = {2023-01-01},
abstract = {Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory state is a finite dimensional quantum state, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory state is a finite dimensional quantum state, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.
60.
Samson Wang, Sam McArdle, Mario Berta
Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T1887,
title = {Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra},
author = {Samson Wang and Sam McArdle and Mario Berta},
url = {https://arxiv.org/abs/2302.01873},
year = {2023},
date = {2023-01-01},
abstract = {We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. For $N times N$ Hermitian matrices, the space cost is $łog(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. For $N times N$ Hermitian matrices, the space cost is $łog(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.
61.
Felix Huber, Nikolai Wyderka
Refuting spectral compatibility of quantum marginals Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T9488,
title = {Refuting spectral compatibility of quantum marginals},
author = {Felix Huber and Nikolai Wyderka},
url = {https://arxiv.org/abs/2211.06349},
year = {2023},
date = {2023-01-01},
abstract = {The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry-reduced semidefinite programming hierarchy for detecting incompatible spectra. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension-free, certifying incompatibility in all local dimensions. The hierarchy equally applies to the sums of Hermitian matrices problem, to optimize trace polynomials on the positive cone, to the compatibility of invariants, and to certify vanishing Kronecker coefficients.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
The spectral variant of the quantum marginal problem asks: Given prescribed spectra for a set of quantum marginals, does there exist a compatible joint state? The main idea of this work is a symmetry-reduced semidefinite programming hierarchy for detecting incompatible spectra. The hierarchy is complete, in the sense that it detects every incompatible set of spectra. The refutations it provides are dimension-free, certifying incompatibility in all local dimensions. The hierarchy equally applies to the sums of Hermitian matrices problem, to optimize trace polynomials on the positive cone, to the compatibility of invariants, and to certify vanishing Kronecker coefficients.
62.
Ulysse Chabaud, Mattia Walschaers
Resources for bosonic quantum computational advantage Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T6568,
title = {Resources for bosonic quantum computational advantage},
author = {Ulysse Chabaud and Mattia Walschaers},
url = {https://arxiv.org/abs/2207.11781},
year = {2023},
date = {2023-01-01},
abstract = {Quantum computers promise to dramatically outperform their classical counterparts. However, the non-classical resources enabling such computational advantages are challenging to pinpoint, as it is not a single resource but the subtle interplay of many that can be held responsible for these potential advantages. In this work, we show that every bosonic quantum computation can be recast into a continuous-variable sampling computation where all computational resources are contained in the input state. Using this reduction, we derive a general classical algorithm for the strong simulation of bosonic computations, whose complexity scales with the non-Gaussian stellar rank of both the input state and the measurement setup. We further study the conditions for an efficient classical simulation of the associated continuous-variable sampling computations and identify an operational notion of non-Gaussian entanglement based on the lack of passive separability, thus clarifying the interplay of bosonic quantum computational resources such as squeezing, non-Gaussianity and entanglement.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Quantum computers promise to dramatically outperform their classical counterparts. However, the non-classical resources enabling such computational advantages are challenging to pinpoint, as it is not a single resource but the subtle interplay of many that can be held responsible for these potential advantages. In this work, we show that every bosonic quantum computation can be recast into a continuous-variable sampling computation where all computational resources are contained in the input state. Using this reduction, we derive a general classical algorithm for the strong simulation of bosonic computations, whose complexity scales with the non-Gaussian stellar rank of both the input state and the measurement setup. We further study the conditions for an efficient classical simulation of the associated continuous-variable sampling computations and identify an operational notion of non-Gaussian entanglement based on the lack of passive separability, thus clarifying the interplay of bosonic quantum computational resources such as squeezing, non-Gaussianity and entanglement.
63.
Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, Seiichiro Tani
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection Conference
2023.
Abstract | Tags: Thursday | Links:
@Conference{T6430,
title = {Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection},
author = {Ryo Hiromasa and Akihiro Mizutani and Yuki Takeuchi and Seiichiro Tani},
url = {https://arxiv.org/abs/2206.05434},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We define rewinding operators that invert quantum measurements. Then, we define complexity classes $latex sf RwBQP$, $latex sf CBQP$, and $latex sf AdPostBQP$ as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that $latex sf BPP^sf PP subseteq sf RwBQP = sf CBQP = sf AdPostBQP subseteq sf PSPACE$. As a byproduct of this result, we show that any problem in $latex sf PostBQP$ can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that $latex sf BQP nsupseteq sf SZK$, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.},
howpublished = {Talk and Proceedings},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Conference}
}
We define rewinding operators that invert quantum measurements. Then, we define complexity classes $latex sf RwBQP$, $latex sf CBQP$, and $latex sf AdPostBQP$ as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that $latex sf BPP^sf PP subseteq sf RwBQP = sf CBQP = sf AdPostBQP subseteq sf PSPACE$. As a byproduct of this result, we show that any problem in $latex sf PostBQP$ can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that $latex sf BQP nsupseteq sf SZK$, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.
64.
Aadil Oufkir
Sample-Optimal Quantum Process Tomography with Non-Adaptive Incoherent Measurements Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T1682,
title = {Sample-Optimal Quantum Process Tomography with Non-Adaptive Incoherent Measurements},
author = {Aadil Oufkir},
url = {https://arxiv.org/abs/2301.12925},
year = {2023},
date = {2023-01-01},
abstract = {How many copies of a quantum process are necessary and sufficient to construct an approximate classical description of it? We extend the result of Surawy-Stepney, Kahn, Kueng, and Guta (2022) to show that $tildemathcalO(din^3dout^3/ε^2)$ copies are sufficient to learn any quantum channel $mathdsC^dintimes dinrightarrowmathdsC^douttimes dout$ to within ε in diamond norm. Moreover, we show that $Ømega(din^3dout^3/ε^2)$ copies are necessary for any strategy using incoherent non-adaptive measurements. This lower bound applies even for ancilla-assisted strategies.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
How many copies of a quantum process are necessary and sufficient to construct an approximate classical description of it? We extend the result of Surawy-Stepney, Kahn, Kueng, and Guta (2022) to show that $tildemathcalO(din^3dout^3/ε^2)$ copies are sufficient to learn any quantum channel $mathdsC^dintimes dinrightarrowmathdsC^douttimes dout$ to within ε in diamond norm. Moreover, we show that $Ømega(din^3dout^3/ε^2)$ copies are necessary for any strategy using incoherent non-adaptive measurements. This lower bound applies even for ancilla-assisted strategies.
65.
Martin Sandfuchs, Marcus Haberland, V. Vilasini, Ramona Wolf
Security of differential phase shift QKD from relativistic principles Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T686,
title = {Security of differential phase shift QKD from relativistic principles},
author = {Martin Sandfuchs and Marcus Haberland and V. Vilasini and Ramona Wolf},
url = {https://arxiv.org/abs/2301.11340},
year = {2023},
date = {2023-01-01},
abstract = {The design of quantum protocols for secure key generation poses many challenges: On the one hand, they need to be practical concerning experimental realisations. On the other hand, their theoretical description must be simple enough to allow for a security proof against all possible attacks. Often, these two requirements are in conflict with each other, and the differential phase shift (DPS) QKD protocol exemplifies these difficulties: It is designed to be implementable with current optical telecommunication technology, which, for this protocol, comes at the cost that many standard security proof techniques do not apply to it. After about 20 years since its invention, this work presents the first full security proof of DPS QKD against general attacks, including finite-size effects. The proof combines techniques from quantum information theory, quantum optics, and relativity. We first give a security proof of a QKD protocol whose security stems from relativistic constraints. We then show that security of DPS QKD can be reduced to security of the relativistic protocol. In addition, we show that coherent attacks on the DPS protocol are, in fact, stronger than collective attacks.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
The design of quantum protocols for secure key generation poses many challenges: On the one hand, they need to be practical concerning experimental realisations. On the other hand, their theoretical description must be simple enough to allow for a security proof against all possible attacks. Often, these two requirements are in conflict with each other, and the differential phase shift (DPS) QKD protocol exemplifies these difficulties: It is designed to be implementable with current optical telecommunication technology, which, for this protocol, comes at the cost that many standard security proof techniques do not apply to it. After about 20 years since its invention, this work presents the first full security proof of DPS QKD against general attacks, including finite-size effects. The proof combines techniques from quantum information theory, quantum optics, and relativity. We first give a security proof of a QKD protocol whose security stems from relativistic constraints. We then show that security of DPS QKD can be reduced to security of the relativistic protocol. In addition, we show that coherent attacks on the DPS protocol are, in fact, stronger than collective attacks.
66.
John Calsamiglia, Marco Fanizza, Christoph Hirche, Yonglong Li, Esteban Martínez Vargas, Ramon Muñoz-Tapia, Gael Sentis, Michalis Skotiniotis, Vincent Tan, Marco Tomamichel
Sequential Methods in Quantum Hypothesis Testing Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T5807,
title = {Sequential Methods in Quantum Hypothesis Testing},
author = {John Calsamiglia and Marco Fanizza and Christoph Hirche and Yonglong Li and Esteban Martínez Vargas and Ramon Muñoz-Tapia and Gael Sentis and Michalis Skotiniotis and Vincent Tan and Marco Tomamichel},
url = {https://arxiv.org/abs/2208.03265 https://arxiv.org/abs/2104.14706},
year = {2023},
date = {2023-01-01},
abstract = {The task of testing the validity of a hypothesis underlies numerous applications in quantum information theory. The most commonly investigated approach is that of gathering all the available (quantum) data and making a final decision based on a collective measurement. However, such offline strategies are often far from practical, both in the amount of data required as well as in the complexity of the required measurement. In some settings, when the goal is quick detection, offline algorithms are not applicable at all, as they can only make a decision once all samples are received. Sequential methods offer the use of online strategies, where samples are requested on a need-to-know basis, drastically reducing the number of required samples in order to guarantee the, task specific, associated performance criteria. While extensively investigated and applied in the classical setting, we know far less about the optimal performance of such online strategies when quantum data is available. In this joint submission we present major recent progress on sequential methods for the fundamental tasks of quantum state discrimination, channel discrimination and quickest change point detection. In summary, we provide a comprehensive picture of the optimal asymptotic performance of online strategies in these settings under different performance criteria.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
The task of testing the validity of a hypothesis underlies numerous applications in quantum information theory. The most commonly investigated approach is that of gathering all the available (quantum) data and making a final decision based on a collective measurement. However, such offline strategies are often far from practical, both in the amount of data required as well as in the complexity of the required measurement. In some settings, when the goal is quick detection, offline algorithms are not applicable at all, as they can only make a decision once all samples are received. Sequential methods offer the use of online strategies, where samples are requested on a need-to-know basis, drastically reducing the number of required samples in order to guarantee the, task specific, associated performance criteria. While extensively investigated and applied in the classical setting, we know far less about the optimal performance of such online strategies when quantum data is available. In this joint submission we present major recent progress on sequential methods for the fundamental tasks of quantum state discrimination, channel discrimination and quickest change point detection. In summary, we provide a comprehensive picture of the optimal asymptotic performance of online strategies in these settings under different performance criteria.
67.
Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, Hakop Pashayan
Shallow shadows: Expectation estimation using low-depth random Clifford circuits Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T4158,
title = {Shallow shadows: Expectation estimation using low-depth random Clifford circuits},
author = {Christian Bertoni and Jonas Haferkamp and Marcel Hinsche and Marios Ioannou and Jens Eisert and Hakop Pashayan},
url = {https://arxiv.org/abs/2209.12924},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
abstract = {We provide practical and powerful schemes for learning properties of a quantum state using a small number of measurements. Specifically, we present a randomized measurement scheme modulated by the depth of a random quantum circuit in one spatial dimension. This scheme interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. We focus on the regime where depth scales logarithmically in the system size and provide evidence that this retains the desirable sample complexity properties of both extremal schemes while also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We achieve our findings by bringing together tools of shadow estimation, random circuits, and tensor networks.},
howpublished = {Talk (merged)},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
We provide practical and powerful schemes for learning properties of a quantum state using a small number of measurements. Specifically, we present a randomized measurement scheme modulated by the depth of a random quantum circuit in one spatial dimension. This scheme interpolates between two known classical shadows schemes based on random Pauli measurements and random Clifford measurements. We focus on the regime where depth scales logarithmically in the system size and provide evidence that this retains the desirable sample complexity properties of both extremal schemes while also being experimentally feasible. We present methods for two key tasks; estimating expectation values of certain observables from generated classical shadows and, computing upper bounds on the depth-modulated shadow norm, thus providing rigorous guarantees on the accuracy of the output estimates. We achieve our findings by bringing together tools of shadow estimation, random circuits, and tensor networks.
68.
Llorenc Escola Farras, Florian Speelman
Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T8860,
title = {Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers},
author = {Llorenc Escola Farras and Florian Speelman},
url = {https://arxiv.org/abs/2212.03674},
year = {2023},
date = {2023-01-01},
abstract = {We give a tight characterization of the relation between loss-tolerance and error rate of the most popular protocol for quantum position verification (QPV), which is based on BB84 states, and generalizations of this protocol. Combining it with classical information, we show for the first time a fault-tolerant protocol that is secure against attackers who pre-share a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss-tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent QKD protocols.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
We give a tight characterization of the relation between loss-tolerance and error rate of the most popular protocol for quantum position verification (QPV), which is based on BB84 states, and generalizations of this protocol. Combining it with classical information, we show for the first time a fault-tolerant protocol that is secure against attackers who pre-share a linear amount of entanglement (in the classical information), arbitrarily slow quantum information and that tolerates a certain amount of photon loss. We also extend this analysis to the case of more than two bases, showing even stronger loss-tolerance for that case. Finally, we show that our techniques can be applied to improve the analysis of one-sided device-independent QKD protocols.
69.
Senrui Chen, Yunchao Liu, Matthew Otten, Alireza Seif, Bill Fefferman, Liang Jiang
The learnability of Pauli noise Workshop
2023.
Abstract | Tags: Friday | Links:
@Workshop{T5371,
title = {The learnability of Pauli noise},
author = {Senrui Chen and Yunchao Liu and Matthew Otten and Alireza Seif and Bill Fefferman and Liang Jiang},
url = {https://arxiv.org/abs/2206.06362 https://tqc-conference.org/wp-content/uploads/cfdb7_uploads/1688149277-poster-TQC_Learnability_Pauli.pdf},
year = {2023},
date = {2023-01-01},
abstract = {Recently, several quantum benchmarking algorithms have been developed to characterize noisy quantum gates on today's quantum devices. A well-known issue in benchmarking is that not everything about quantum noise is learnable due to the existence of gauge freedom, leaving open the question of what information about noise is learnable and what is not, which has been unclear even for a single CNOT gate. Here we give a precise characterization of the learnability of Pauli noise channels attached to Clifford gates, showing that learnable information corresponds to the cycle space of the pattern transfer graph of the gate set, while unlearnable information corresponds to the cut space. This implies the optimality of cycle benchmarking, in the sense that it can learn all learnable information about Pauli noise. We experimentally demonstrate noise characterization of IBM's CNOT gate up to 2 unlearnable degrees of freedom, for which we obtain bounds using physical constraints. In addition, we give an attempt to characterize the unlearnable information by assuming perfect initial state preparation. However, based on the experimental data, we conclude that this assumption is inaccurate as it yields unphysical estimates, and we obtain a lower bound on state preparation noise.},
howpublished = {Talk},
keywords = {Friday},
pubstate = {published},
tppubtype = {Workshop}
}
Recently, several quantum benchmarking algorithms have been developed to characterize noisy quantum gates on today's quantum devices. A well-known issue in benchmarking is that not everything about quantum noise is learnable due to the existence of gauge freedom, leaving open the question of what information about noise is learnable and what is not, which has been unclear even for a single CNOT gate. Here we give a precise characterization of the learnability of Pauli noise channels attached to Clifford gates, showing that learnable information corresponds to the cycle space of the pattern transfer graph of the gate set, while unlearnable information corresponds to the cut space. This implies the optimality of cycle benchmarking, in the sense that it can learn all learnable information about Pauli noise. We experimentally demonstrate noise characterization of IBM's CNOT gate up to 2 unlearnable degrees of freedom, for which we obtain bounds using physical constraints. In addition, we give an attempt to characterize the unlearnable information by assuming perfect initial state preparation. However, based on the experimental data, we conclude that this assumption is inaccurate as it yields unphysical estimates, and we obtain a lower bound on state preparation noise.
70.
Giulio Chiribella, Fei Meng, Renato Renner, Man-Hong Yung
The nonequilibrium cost of accurate information processing Workshop
2023.
Abstract | Tags: Tuesday | Links:
@Workshop{T1396,
title = {The nonequilibrium cost of accurate information processing},
author = {Giulio Chiribella and Fei Meng and Renato Renner and Man-Hong Yung},
url = {https://www.nature.com/articles/s41467-022-34541-w},
year = {2023},
date = {2023-01-01},
abstract = {Accurate information processing is crucial both in technology and in nature. To achieve it, any information processing system needs an initial supply of resources away from thermal equilibrium. Here we establish a fundamental limit on the accuracy achievable with a given amount of nonequilibrium resources. The limit applies to arbitrary information processing tasks and arbitrary information processing systems subject to the laws of quantum mechanics. It is easily computable and is expressed in terms of an entropic quantity, which we name the reverse entropy, associated to a time reversal of the information processing task under consideration. The limit is achievable for all deterministic classical computations and for all their quantum extensions. As an application, we establish the optimal tradeoff between nonequilibrium and accuracy for the fundamental tasks of storing, transmitting, cloning, and erasing information. Our results set a target for the design of new devices approaching the ultimate efficiency limit, and provide a framework for demonstrating thermodynamical advantages of quantum devices over their classical counterparts. This also implies a thermodynamic benchmark to certify genuine quantum devices from their classical simulation.},
howpublished = {Talk},
keywords = {Tuesday},
pubstate = {published},
tppubtype = {Workshop}
}
Accurate information processing is crucial both in technology and in nature. To achieve it, any information processing system needs an initial supply of resources away from thermal equilibrium. Here we establish a fundamental limit on the accuracy achievable with a given amount of nonequilibrium resources. The limit applies to arbitrary information processing tasks and arbitrary information processing systems subject to the laws of quantum mechanics. It is easily computable and is expressed in terms of an entropic quantity, which we name the reverse entropy, associated to a time reversal of the information processing task under consideration. The limit is achievable for all deterministic classical computations and for all their quantum extensions. As an application, we establish the optimal tradeoff between nonequilibrium and accuracy for the fundamental tasks of storing, transmitting, cloning, and erasing information. Our results set a target for the design of new devices approaching the ultimate efficiency limit, and provide a framework for demonstrating thermodynamical advantages of quantum devices over their classical counterparts. This also implies a thermodynamic benchmark to certify genuine quantum devices from their classical simulation.
71.
David Rasmussen Lolck, Laura Mančinska, Simon Schmidt, Thor Nielsen, Jed Kaniewski
The power and limitations of self-testing Workshop
2023.
Abstract | Tags: Wednesday | Links:
@Workshop{T755,
title = {The power and limitations of self-testing},
author = {David Rasmussen Lolck and Laura Mančinska and Simon Schmidt and Thor Nielsen and Jed Kaniewski},
url = {https://github.com/Derzeed/Strengths-and-limitations-of-Self-Testing/blob/main/Strengths-and-limitations.pdf},
year = {2023},
date = {2023-01-01},
abstract = {Self-testing results allow us to characterize measurements and states in a quantum device from classical output probabilities in a nonlocal game. However, there is some variation in how the individual self- testing statements are stated and proven, including whether they apply robustly or assume purity of the state or protectiveness of the measurements. We investigate these differences, and as one of our main results show that if the reference strategy of a given game has full Schmidt rank, the notions of self-testing strategies using either mixed or pure states coincide. Additionally, we show by example that not all types of self-testing statements are equivalent: We both provide an example of a nonlocal game which is an exact, but not a robust, self-test, and an example of another game which does not self-test any state.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
Self-testing results allow us to characterize measurements and states in a quantum device from classical output probabilities in a nonlocal game. However, there is some variation in how the individual self- testing statements are stated and proven, including whether they apply robustly or assume purity of the state or protectiveness of the measurements. We investigate these differences, and as one of our main results show that if the reference strategy of a given game has full Schmidt rank, the notions of self-testing strategies using either mixed or pure states coincide. Additionally, we show by example that not all types of self-testing statements are equivalent: We both provide an example of a nonlocal game which is an exact, but not a robust, self-test, and an example of another game which does not self-test any state.
72.
Jonas Helsen, Michael Walter
Thrifty shadow estimation: re-using quantum circuits and bounding tails Workshop
2023.
Abstract | Tags: Monday | Links:
@Workshop{T3723,
title = {Thrifty shadow estimation: re-using quantum circuits and bounding tails},
author = {Jonas Helsen and Michael Walter},
url = {https://arxiv.org/abs/2212.06240},
year = {2023},
date = {2023-01-01},
abstract = {Randomized shadow estimation is a recent protocol that allows estimating exponentially many expectation values of a quantum state from ``classical shadows'', obtained by applying random quantum circuits and computational basis measurements. In this paper we study the statistical efficiency of this approach in light of near-term quantum computing. In particular, we propose and analyze a more practically-implementable variant of the protocol, thrifty shadow estimation, in which quantum circuits are reused many times instead of having to be freshly generated for each measurement (as in the original protocol). We show that the effect of this reuse strongly depends on the family of quantum circuits that is chosen. In particular, it is maximally effective when sampling Haar random unitaries, and maximally ineffective when sampling Clifford circuits (even though the Clifford group forms a three-design). To interpolate between these two extremes, we provide an efficiently simulable family of quantum circuits inspired by a recent construction of approximate t-designs. Finally we consider tail bounds for shadow estimation and discuss when median-of-means estimation can be replaced with standard mean estimation.},
howpublished = {Talk},
keywords = {Monday},
pubstate = {published},
tppubtype = {Workshop}
}
Randomized shadow estimation is a recent protocol that allows estimating exponentially many expectation values of a quantum state from ``classical shadows'', obtained by applying random quantum circuits and computational basis measurements. In this paper we study the statistical efficiency of this approach in light of near-term quantum computing. In particular, we propose and analyze a more practically-implementable variant of the protocol, thrifty shadow estimation, in which quantum circuits are reused many times instead of having to be freshly generated for each measurement (as in the original protocol). We show that the effect of this reuse strongly depends on the family of quantum circuits that is chosen. In particular, it is maximally effective when sampling Haar random unitaries, and maximally ineffective when sampling Clifford circuits (even though the Clifford group forms a three-design). To interpolate between these two extremes, we provide an efficiently simulable family of quantum circuits inspired by a recent construction of approximate t-designs. Finally we consider tail bounds for shadow estimation and discuss when median-of-means estimation can be replaced with standard mean estimation.
73.
Yingkai Ouyang, Masahito Hayashi
Tight Cramér-Rao type bounds for multiparameter quantum metrology through conic programming Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T7082,
title = {Tight Cramér-Rao type bounds for multiparameter quantum metrology through conic programming},
author = {Yingkai Ouyang and Masahito Hayashi},
url = {https://arxiv.org/abs/2209.05218},
year = {2023},
date = {2023-01-01},
abstract = {In the quest to unlock the maximum potential of quantum sensors, it is of paramount importance to have practical measurement strategies that can estimate incompatible parameters with best precisions possible. However, it is still not known how to find practical measurements with optimal precisions, even for uncorrelated measurements over probe states. Here, we give a concrete way to find uncorrelated measurement strategies with optimal precisions. We solve this fundamental problem by introducing a framework of conic programming that unifies the theory of precision bounds for multiparameter estimates for uncorrelated and correlated measurement strategies under a common umbrella. Namely, we give precision bounds that arise from linear programs on various cones defined on a tensor product space of matrices, including a particular cone of separable matrices. Subsequently, our theory allows us to develop an efficient algorithm that calculates both upper and lower bounds for the ultimate precision bound for uncorrelated measurement strategies, where these bounds can be tight. In particular, the uncorrelated measurement strategy that arises from our theory saturates the upper bound to the ultimate precision bound. Also, we show numerically that there is a strict gap between the previous efficiently computable bounds and the ultimate precision bound.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
In the quest to unlock the maximum potential of quantum sensors, it is of paramount importance to have practical measurement strategies that can estimate incompatible parameters with best precisions possible. However, it is still not known how to find practical measurements with optimal precisions, even for uncorrelated measurements over probe states. Here, we give a concrete way to find uncorrelated measurement strategies with optimal precisions. We solve this fundamental problem by introducing a framework of conic programming that unifies the theory of precision bounds for multiparameter estimates for uncorrelated and correlated measurement strategies under a common umbrella. Namely, we give precision bounds that arise from linear programs on various cones defined on a tensor product space of matrices, including a particular cone of separable matrices. Subsequently, our theory allows us to develop an efficient algorithm that calculates both upper and lower bounds for the ultimate precision bound for uncorrelated measurement strategies, where these bounds can be tight. In particular, the uncorrelated measurement strategy that arises from our theory saturates the upper bound to the ultimate precision bound. Also, we show numerically that there is a strict gap between the previous efficiently computable bounds and the ultimate precision bound.
74.
Laura Clinton, Toby Cubitt, Brian Flynn, Filippo Maria Gambetta, Joel Klassen, Ashley Montanaro, Stephen Piddock, Raul A. Santos, Evan Sheridan
Towards near-term quantum simulation of materials Workshop
2023.
@Workshop{T8983,
title = {Towards near-term quantum simulation of materials},
author = {Laura Clinton and Toby Cubitt and Brian Flynn and Filippo Maria Gambetta and Joel Klassen and Ashley Montanaro and Stephen Piddock and Raul A. Santos and Evan Sheridan},
year = {2023},
date = {2023-01-01},
abstract = {The limiting constraint on simulating materials on near-term quantum hardware is the requisite circuit depths and qubit numbers, with current estimates placing them well beyond near-term capabilities. A critical subroutine of simulation algorithms is implementing a layer of unitary evolutions by each local term in the Hamiltonian. In this work we develop a new quantum algorithm which dramatically reduces the estimated cost of material simulations using this subroutine, improving circuit depths by up to 6 orders of magnitude for Strontium Vanadate, for example. We achieve this by introducing a fermionic encoding that leverages the locality of materials Hamiltonians describing an active space in the Wannier basis. This design generates quantum circuits whose depth is independent of the system’s size.},
howpublished = {Talk},
keywords = {Wednesday},
pubstate = {published},
tppubtype = {Workshop}
}
The limiting constraint on simulating materials on near-term quantum hardware is the requisite circuit depths and qubit numbers, with current estimates placing them well beyond near-term capabilities. A critical subroutine of simulation algorithms is implementing a layer of unitary evolutions by each local term in the Hamiltonian. In this work we develop a new quantum algorithm which dramatically reduces the estimated cost of material simulations using this subroutine, improving circuit depths by up to 6 orders of magnitude for Strontium Vanadate, for example. We achieve this by introducing a fermionic encoding that leverages the locality of materials Hamiltonians describing an active space in the Wannier basis. This design generates quantum circuits whose depth is independent of the system’s size.
75.
Satoshi Yoshida, Akihito Soeda, Mio Murao
Universal, deterministic, and exact protocol to reverse qubit-unitary and qubit-encoding isometry operations Workshop
2023.
Abstract | Tags: Thursday | Links:
@Workshop{T1434,
title = {Universal, deterministic, and exact protocol to reverse qubit-unitary and qubit-encoding isometry operations},
author = {Satoshi Yoshida and Akihito Soeda and Mio Murao},
url = {https://arxiv.org/abs/2209.02907},
year = {2023},
date = {2023-01-01},
abstract = {In this work, we report a deterministic and exact protocol to reverse any unknown qubit-unitary and qubit-encoding isometry operations. We present the semidefinite programming (SDP) to search the Choi matrix representing a quantum circuit reversing any unitary operation. We derive a quantum circuit transforming four calls of any qubit-unitary operation into its inverse operation by imposing the SU(2)×SU(2) symmetry on the Choi matrix. This protocol only applies only for qubit-unitary operations, but we extend this protocol to any qubit-encoding isometry operations. For that, we derive a subroutine to transform a unitary inversion protocol to an isometry inversion protocol by constructing a quantum circuit transforming finite sequential calls of any isometry operation into random unitary operations.},
howpublished = {Talk},
keywords = {Thursday},
pubstate = {published},
tppubtype = {Workshop}
}
In this work, we report a deterministic and exact protocol to reverse any unknown qubit-unitary and qubit-encoding isometry operations. We present the semidefinite programming (SDP) to search the Choi matrix representing a quantum circuit reversing any unitary operation. We derive a quantum circuit transforming four calls of any qubit-unitary operation into its inverse operation by imposing the SU(2)×SU(2) symmetry on the Choi matrix. This protocol only applies only for qubit-unitary operations, but we extend this protocol to any qubit-encoding isometry operations. For that, we derive a subroutine to transform a unitary inversion protocol to an isometry inversion protocol by constructing a quantum circuit transforming finite sequential calls of any isometry operation into random unitary operations.
