Author name cluster

Atul Singh Arora

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

FOCS Conference 2024 Conference Paper

A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness

Atul Singh Arora
Kishor Bharti
Alexandru Cojocaru
Andrea Coladangelo

Bell non-locality is a fundamental feature of quantum mechanics whereby measurements performed on “spatially separated” quantum systems can exhibit correlations that cannot be understood as revealing predetermined values. This is a special case of the more general phenomenon of “quantum contextuality”, which says that such correlations can occur even when the measurements are not necessarily on separate quantum systems, but are merely “compatible” (i. e. commuting). Crucially, while any non-local game yields an experiment that demonstrates quantum advantage by leveraging the “spatial separation” of two or more devices (and in fact several such demonstrations have been conducted successfully in recent years), the same is not true for quantum contextuality: finding the contextuality analogue of such an experiment is arguably one of the central open questions in the foundations of quantum mechanics. In this work, we show that an arbitrary contextuality game can be compiled into an “operational test of contextuality” involving a single quantum device, by only making the assumption that the device is computationally bounded. Our work is inspired by the recent work of Kalai et al. (STOC '23) that converts any non-local game into a classical test of quantum advantage with a single device. The central idea in their work is to use cryptography to enforce spatial separation within subsystems of a single quantum device. Our work can be seen as using cryptography to enforce “temporal separation”, i. e. to restrict communication between sequential measurements. Beyond contextuality, we employ our ideas to design a “proof of quantumness” that, to the best of our knowledge, is arguably even simpler than the ones proposed in the literature so far.

Details

STOC Conference 2023 Conference Paper

Quantum Depth in the Random Oracle Model

Atul Singh Arora
Andrea Coladangelo
Matthew Coudron
Alexandru Gheorghiu
Uttam Singh
Hendrik Waldner

We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle: (a) BPP QNC BPP ≠ BQP . This refutes Jozsa’s conjecture 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) BPP QNC ⊈ QNC BPP and QNC BPP ⊈ BPP QNC . 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. We also show that BPP QNC and BPP QNC are both strictly contained in BPP QNC BPP . (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.

Details

SODA Conference 2021 Conference Paper

Analytic quantum weak coin flipping protocols with arbitrarily small bias

Atul Singh Arora
Jérémie Roland
Chrysoula Vlachou

Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias ∊ if neither party can force their preferred outcome with probability greater than 1/2 + ∊. Classical WCF protocols are shown to have bias 1/2, i. e. , a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv: 0711. 4114]. In particular, he proved the existence of a family of WCF protocols approaching bias ∊ ( k ) = 1/(4 k +2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p. 205–216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias 1/14.

Details

STOC Conference 2019 Conference Paper

Quantum weak coin flipping

Atul Singh Arora
Jérémie Roland
Stephan Weis

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. For weak coin flipping the players have known opposite preferred values. A weak coin-flipping protocol has a bias є if neither player can force the outcome towards their preferred value with probability more than 1/2+є. While it is known that all classical protocols have є=1/2, Mochon showed in 2007 that quantumly weak coin flipping can be achieved with arbitrarily small bias (near perfect) but the former best known explicit protocol has bias 1/6 (also due to Mochon, 2005). We propose a framework to construct new explicit protocols achieving biases below 1/6. In particular, we construct explicit unitaries for protocols with bias down to 1/10. To go lower, we introduce what we call the Elliptic Monotone Align (EMA) algorithm which, together with the framework, allows us to construct protocols with arbitrarily small biases.

Details