Mario Szegedy
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Mario Szegedy has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Miklos Santha
And Centre for Quantum Technologies CNRS -LRI Université Paris-Sud Orsay France
2 shared publications - Ronald de Wolf
QuSoft CWI University of Amsterdam the Netherlands
2 shared publications - Sergey Bravyi
IBM T.J. Watson Research Center
2 shared publications - Sophie Laplante
LRI, Bâtiment 490, Université Paris-Sud, Orsay Cedex, France
2 shared publications - Troy Lee
CWI and University of Amsterdam, Amsterdam, The Netherlands
2 shared publications - Yash Sharma
Rutgers University
2 shared publications
Latest Publications
- Open Access
Connecting Quantum Computing with Classical Stochastic Simulation
This tutorial paper introduces quantum approaches to Monte Carlo computation with applications in computational finance. We outline the basics of quantum computing using Grover's algorithm for unstructured search to build intuition. We then move slowly to amplitude estimation problems and applications to counting and Monte Carlo integration, again using Grover-type iterations. A hands-on Python/Qiskit implementation illustrates these concepts applied to finance. The paper concludes with a discussion on current challenges in scaling quantum simulation techniques.
Open AccessConnecting Quantum Computing with Classical Stochastic Simulation
This tutorial paper introduces quantum approaches to Monte Carlo computation with applications in computational finance. We outline the basics of quantum computing using Grover's algorithm for unstructured search to build intuition. We then move slowly to amplitude estimation problems and applications to counting and Monte Carlo integration, again using Grover-type iterations. A hands-on Python/Qiskit implementation illustrates these concepts applied to finance. The paper concludes with a discussion on current challenges in scaling quantum simulation techniques.
- Open Access
- 14 May 2024
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 8, 1348
Generating k EPR-pairs from an n -party resource state
Motivated by quantum network applications over classical channels, we initiate the study of n -party resource states from which LOCC protocols can create EPR-pairs between any k disjoint pairs of parties. We give constructions of such states where k is not too far from the optimal n / 2 while the individual parties need to hold only a constant number of qubits. In the special case when each party holds only one qubit, we describe a family of n -qubit states with k proportional to log n based on Reed-Muller codes, as well as small numerically found examples for k = 2 and k = 3 . We also prove some lower bounds, for example showing that if k = n / 2 then the parties must have at least Ω ( log log n ) qubits each.
- 14 May 2024
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 8, 1348
Open AccessGenerating k EPR-pairs from an n -party resource state
Motivated by quantum network applications over classical channels, we initiate the study of n -party resource states from which LOCC protocols can create EPR-pairs between any k disjoint pairs of parties. We give constructions of such states where k is not too far from the optimal n / 2 while the individual parties need to hold only a constant number of qubits. In the special case when each party holds only one qubit, we describe a family of n -qubit states with k proportional to log n based on Reed-Muller codes, as well as small numerically found examples for k = 2 and k = 3 . We also prove some lower bounds, for example showing that if k = n / 2 then the parties must have at least Ω ( log log n ) qubits each.
- Open AccessGenerating $k$ EPR-pairs from an $n$-party resource stateMotivated by quantum network applications over classical channels, we initiate the study of $n$-party resource states from which LOCC protocols can create EPR-pairs between any $k$ disjoint pairs of parties. We give constructions of such states where $k$ is not too far from the optimal $n/2$ while the individual parties need to hold only a constant number of qubits. In the special case when each party holds only one qubit, we describe a family of $n$-qubit states with $k$ proportional to $\log n$ based on Reed-Muller codes, as well as small numerically found examples for $k=2$ and $k=3$. We also prove some lower bounds, for example showing that if $k=n/2$ then the parties must have at least $\Omega(\log\log n)$ qubits each.Open AccessGenerating $k$ EPR-pairs from an $n$-party resource stateMotivated by quantum network applications over classical channels, we initiate the study of $n$-party resource states from which LOCC protocols can create EPR-pairs between any $k$ disjoint pairs of parties. We give constructions of such states where $k$ is not too far from the optimal $n/2$ while the individual parties need to hold only a constant number of qubits. In the special case when each party holds only one qubit, we describe a family of $n$-qubit states with $k$ proportional to $\log n$ based on Reed-Muller codes, as well as small numerically found examples for $k=2$ and $k=3$. We also prove some lower bounds, for example showing that if $k=n/2$ then the parties must have at least $\Omega(\log\log n)$ qubits each.
- 19 August 2015
- Published by Springer Nature in Algorithmica
- Vol. 76 (2) , 490-501
Streaming Algorithms for Independent Sets in Sparse Hypergraphs
- 19 August 2015
- Published by Springer Nature in Algorithmica
- Vol. 76 (2) , 490-501
Streaming Algorithms for Independent Sets in Sparse Hypergraphs
- Open AccessAn $O(n^{0.4732})$ upper bound on the complexity of the GKS communication gameWe give an $5\cdot n^{\log_{30}5}$ upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their $\sqrt{999\over 1000}\sqrt{n}$ bound. We also determine the exact complexity of the game up to $n\le 9$.Open AccessAn $O(n^{0.4732})$ upper bound on the complexity of the GKS communication gameWe give an $5\cdot n^{\log_{30}5}$ upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their $\sqrt{999\over 1000}\sqrt{n}$ bound. We also determine the exact complexity of the game up to $n\le 9$.
- Open Access
A simplified proof of a Lee-Yang type theorem
In this short note, we give a simple proof of a Lee-Yang type theorem which appeared in "Lee-Yang theorems and the complexity of computing averages" by Alistair Sinclair and Piyush Srivastava.
Open AccessA simplified proof of a Lee-Yang type theorem
In this short note, we give a simple proof of a Lee-Yang type theorem which appeared in "Lee-Yang theorems and the complexity of computing averages" by Alistair Sinclair and Piyush Srivastava.
- Open Access
The Garden Hose Complexity for the Equality Function
The garden hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman [BFSS13] to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of O. Margalit and A. Matsliah[MM12] with the help of a new approach and of our handmade simulated annealing based solver. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of garden hose permutation groups. Then, exploiting this new concept, we get even further, although several interesting open problems remain.
Open AccessThe Garden Hose Complexity for the Equality Function
The garden hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman [BFSS13] to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of O. Margalit and A. Matsliah[MM12] with the help of a new approach and of our handmade simulated annealing based solver. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of garden hose permutation groups. Then, exploiting this new concept, we get even further, although several interesting open problems remain.
- 26 July 2013
- Published by Springer Nature
- p. 2625-2683
Probabilistic Verification and Non-approximability
- 26 July 2013
- Published by Springer Nature
- p. 2625-2683
Probabilistic Verification and Non-approximability
- Open Access
Quantum query complexity of state conversion
State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.
Open AccessQuantum query complexity of state conversion
State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.