Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On Invertible Sampling and Adaptive Security

Yuval Ishai, Abishek Kumarasubramanian, Claudio Orlandi, Amit Sahai

Published Jan 1, 2010• 15 citations
Publisher
DOI
10.1007/978-3-642-17373-8_27

Related papers

Simpler Proofs of Quantumness

Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani +1 more

A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor's algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

arXiv:2005.04826•Leibniz international proceedings in informatics•Jan 1, 2020•60 citations

Adaptively Secure Coin-Flipping, Revisited

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

Lecture notes in computer science•Jan 1, 2015•18 citations

Self-Adaptive Gate Control for Efficient Escape From Local Minimum Energy on Invertible Logic

Naoya Onizawa, Koji Yano, Seiichi Shin +2 more

Invertible logic can realize bidirectional operations of a function represented by a Hamiltonian (energy) with noise and can be applied for integer factorization and training neural networks. However, the computation error is not negligible due to becoming trapped at the local minimum energy when the Hamiltonian is large. This paper introduces self-adaptive gate control (SAGC) for high convergence rates to the global minimum energy on invertible logic. From our analysis based on simulating small-scale invertible logic circuits, it is supposed that becoming stuck is caused by invalid states of invertible gates. The proposed SAGC autonomously detects invalid gates by checking the truth tables and adds large noise to them for efficient escape from the local minimum energy. As a typical example of invertible logic, invertible adders, multipliers and multiplexers are designed and evaluated. The simulation results show that the convergence probabilities to the global minimum based on SAGC are a few times higher than those based on a conventional method that equally adds noise to all the gates.

IEEE Access•Jan 1, 2023•0 citations

On Adaptively Secure Protocols

Muthuramakrishnan Venkitasubramaniam

Lecture notes in computer science•Jan 1, 2014•13 citations

Adaptive Security with Quasi-Optimal Rate

Brett Hemenway, Rafail Ostrovsky, Silas Richelson +1 more

Lecture notes in computer science•Dec 18, 2015•10 citations

Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup

Rawad Mezher, Joe Ghalbouni, Joseph Dgheim +1 more

At its core a $t$-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics. We construct new families of quantum circuits on $n$-qubits giving rise to $\varepsilon$-approximate unitary $t$-designs efficiently in $O(n^3t^{12})$ depth. These quantum circuits are based on a relaxation of technical requirements in previous constructions. In particular, the construction of circuits which give efficient approximate $t$-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M. Horodecki, Commun. Math. Phys. (2016).) required choosing gates from ensembles which contained inverses for all elements, and that the entries of the unitaries are algebraic. We reduce these requirements, to sets that contain elements without inverses in the set, and non-algebraic entries, which we dub partially invertible universal sets. We then adapt this circuit construction to the framework of measurement based quantum computation(MBQC) and give new explicit examples of $n$-qubit graph states with fixed assignments of measurements (graph gadgets) giving rise to unitary $t$-designs based on partially invertible universal sets, in a natural way. We further show that these graph gadgets demonstrate a quantum speedup, up to standard complexity theoretic conjectures. We provide numerical and analytical evidence that almost any assignment of fixed measurement angles on an $n$-qubit cluster state give efficient $t$-designs and demonstrate a quantum speedup.

arXiv:1905.01504•May 4, 2019•17 citations
A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor's algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.
Invertible logic can realize bidirectional operations of a function represented by a Hamiltonian (energy) with noise and can be applied for integer factorization and training neural networks. However, the computation error is not negligible due to becoming trapped at the local minimum energy when the Hamiltonian is large. This paper introduces self-adaptive gate control (SAGC) for high convergence rates to the global minimum energy on invertible logic. From our analysis based on simulating small-scale invertible logic circuits, it is supposed that becoming stuck is caused by invalid states of invertible gates. The proposed SAGC autonomously detects invalid gates by checking the truth tables and adds large noise to them for efficient escape from the local minimum energy. As a typical example of invertible logic, invertible adders, multipliers and multiplexers are designed and evaluated. The simulation results show that the convergence probabilities to the global minimum based on SAGC are a few times higher than those based on a conventional method that equally adds noise to all the gates.
At its core a ttt-design is a method for sampling from a set of unitaries in a way which mimics sampling randomly from the Haar measure on the unitary group, with applications across quantum information processing and physics. We construct new families of quantum circuits on nnn-qubits giving rise to ε\varepsilonε-approximate unitary ttt-designs efficiently in O(n3t12)O(n^3t^{12})O(n3t12) depth. These quantum circuits are based on a relaxation of technical requirements in previous constructions. In particular, the construction of circuits which give efficient approximate ttt-designs by Brandao, Harrow, and Horodecki (F.G.S.L Brandao, A.W Harrow, and M. Horodecki, Commun. Math. Phys. (2016).) required choosing gates from ensembles which contained inverses for all elements, and that the entries of the unitaries are algebraic. We reduce these requirements, to sets that contain elements without inverses in the set, and non-algebraic entries, which we dub partially invertible universal sets. We then adapt this circuit construction to the framework of measurement based quantum computation(MBQC) and give new explicit examples of nnn-qubit graph states with fixed assignments of measurements (graph gadgets) giving rise to unitary ttt-designs based on partially invertible universal sets, in a natural way. We further show that these graph gadgets demonstrate a quantum speedup, up to standard complexity theoretic conjectures. We provide numerical and analytical evidence that almost any assignment of fixed measurement angles on an nnn-qubit cluster state give efficient ttt-designs and demonstrate a quantum speedup.