166 citations · 435 across the 13 of their papers we have counts for
18 papers · 1 filter
Single-Round Proofs of Quantumness from Knowledge Assumptions
Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton +1
A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptogra…
Nonlocality under Computational Assumptions
Khashayar Barooti, Alexandru Gheorghiu, Grzegorz Głuch +1
Nonlocality and its connections to entanglement are fundamental features of quantum mechanics that have found numerous applications in quantum information science. A set of correla…
Simple Tests of Quantumness Also Certify Qubits
Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer +2
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain templ…
Quantum Depth in the Random Oracle Model
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron +3
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, w…
Experimental Implementation of an Efficient Test of Quantumness
Laura Lewis, Daiwei Zhu, Alexandru Gheorghiu +11
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior, under certain cryptographic ass…
Oracle separations of hybrid quantum-classical circuits
Atul Singh Arora, Alexandru Gheorghiu, Uttam Singh
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computatio…
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more
Alexandru Gheorghiu, Tony Metger, Alexander Poremba
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to b…
Interactive Protocols for Classically-Verifiable Quantum Advantage
Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis +15
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically…
Depth-efficient proofs of quantumness
Zhenning Liu, Alexandru Gheorghiu
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the quantum advantage of an untrusted prover. That is, a quant…
A deep learning model for noise prediction on near-term quantum devices
Alexander Zlokapa, Alexandru Gheorghiu
We present an approach for a deep-learning compiler of quantum circuits, designed to reduce the output noise of circuits run on a specific device. We train a convolutional neural n…
On estimating the entropy of shallow circuit outputs
Alexandru Gheorghiu, Matty J. Hoban
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of p…
Ontological models for quantum theory as functors
Alexandru Gheorghiu, Chris Heunen
We interpret ontological models for finite-dimensional quantum theory as functors from the category of finite-dimensional Hilbert spaces and bounded linear maps to the category of…
Computationally-secure and composable remote state preparation
Alexandru Gheorghiu, Thomas Vidick
We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparatio…
A simple protocol for fault tolerant verification of quantum computation
Alexandru Gheorghiu, Matty J. Hoban, Elham Kashefi
With experimental quantum computing technologies now in their infancy, the search for efficient means of testing the correctness of these quantum computations is becoming more pres…
Verification of quantum computation: An overview of existing approaches
Alexandru Gheorghiu, Theodoros Kapourniotis, Elham Kashefi
Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also cons…
Complexity-theoretic limitations on blind delegated quantum computation
Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu +1
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the sp…
Rigidity of quantum steering and one-sided device-independent verifiable quantum computation
Alexandru Gheorghiu, Petros Wallden, Elham Kashefi
The relationship between correlations and entanglement has played a major role in understanding quantum theory since the work of Einstein, Podolsky and Rosen (1935). Tsirelson (198…
Robustness and device independence of verifiable blind quantum computing
Alexandru Gheorghiu, Elham Kashefi, Petros Wallden
Recent advances in theoretical and experimental quantum computing bring us closer to scalable quantum computing devices. This makes the need for protocols that verify the correct f…