Niraj Kumar

The goal of demonstrating a quantum advantage with currently available experimental systems is of utmost importance in quantum information science. While this remains elusive for quantum computation, the field of communication complexity offers the possibility to already explore and showcase this advantage for useful tasks. Here, we define such a task, the Sampling Matching problem, which is inspired by the Hidden Matching problem and features an exponential gap between quantum and classical protocols in the one-way communication model. Our problem allows by its conception a proof-of-principle photonic implementation based on encoding in the phase of coherent states of light, the use of a fixed size linear optic circuit, and single-photon detection. This enables us to demonstrate experimentally an advantage in the transmitted information resource beyond a threshold input size, which would have been impossible to reach for the original Hidden Matching problem. Our demonstration has implications in various communication and cryptographic settings. Specifically we have used it to introduce a robust practical quantum money-scheme. Our scheme involves an honest Bank who prepares the note by independently and uniformly selecting multiple n-bit binary secret strings which are encoded into the single photon states. The note is then distributed among untrusted holders. To carry out the transaction, the note holder sends the note to the honest local verifiers of the Bank. The verifier runs the Sampling Matching scheme on some randomly selected copies of the note and forwards the classical measurement outcome to the Bank. The Bank then declares the validity of the note. Our private-key money scheme includes multiple features such as single round classical interaction of the local verifier with the Bank, optimal note re-usability (linear in the size of Bank note), linear verification circuit size, and an unconditional security against any adversary trying to forge the Bank note while tolerating the noise of up to 21.4%. The simplistic nature of our verification scheme using Sampling Matching allows for the ability to reach a maximal theoretical noise tolerance of 25%, as conjectured by Amiri et al [Phys Rev A 95, 062334].

Achieving computational advantage using NISQ devices on practically useful problems is a long standing challenge. We report two papers that experimentally demonstrate a concrete application, namely certified randomness generation, which could be useful for multi-party cryptographic protocols and improving imperfect physical sources of randomness. Both papers involve substantial theoretical contributions to the protocol. We devise a realistic protocol that maximizes practical hardness. The verifier first asks the server to prepare a quantum state using a random circuit and then sends a random measurement basis right before the result must be received. This is repeated for many rounds. We show complexity theoretic evidence for entropy generation and provide improved entropy bounds against adversaries with oracle access to the random circuits. We also construct an end-to-end application of randomness amplification of imperfect sources into nearly perfect randomness, notably achieving everlasting security which uplifts computational security to information theoretic security.

Quantum physical unclonable functions, or QPUFs, are rapidly emerging as theoretical hardware solutions to provide secure cryptographic functionalities such as key exchange, message authentication, entity identification among others. Recent works have shown that in order to provide provable security of these solutions against any quantum polynomial time adversary, QPUFs are required to be a unitary sampled uniformly randomly from the Haar measure. This however is known to require an exponential amount of resources. In this work, we propose an efficient construction of these devices using unitary t-designs, called QPUF_t. Along the way, we modify the existing security definitions of QPUFs to include efficient constructions and showcase that QPUF_t still retains the provable security guarantees against a bounded quantum polynomial adversary with t-query access to the device. This also provides the first use case of unitary t-design construction for arbitrary t, as opposed to previous applications of t-designs where usually a few (relatively low) values of t are known to be useful for performing some task. We study the noise-resilience of QPUF_t against specific types of noise, unitary noise, and show that some resilience can be achieved particularly when the error rates affecting individual qubits become smaller as the system size increases. To make the noise resilience more realistic and meaningful, we conclude that some notion of error mitigation or correction should be introduced.

Cryptanalysis of quantum cryptographic systems generally involves finding optimal adversarial attack strategies on the underlying protocols. The core principle of modeling quantum attacks often reduces to the ability of the adversary to clone unknown quantum states and to extract thereby meaningful secret information. Explicit optimal attack strategies typically require high computational resources due to large circuit depths or, in many cases, are unknown. Here we introduce variational quantum cloning (VarQlone), a cryptanalysis algorithm based on quantum machine learning, which allows an adversary to obtain optimal approximate cloning strategies with short depth quantum circuits, trained using hybrid classical-quantum techniques. The algorithm contains operationally meaningful cost functions with theoretical guarantees, quantum circuit structure learning and gradient-descent-based optimization. Our approach enables the end-to-end discovery of hardware-efficient quantum circuits to clone specific families of quantum states, which we demonstrate in implementation on the Rigetti Aspen quantum hardware. We connect these results to quantum cryptographic primitives and derive explicit attacks facilitated by VarQlone. We expect that quantum machine learning will serve as a resource for improving attacks on current and future quantum cryptographic protocols.

Recently, major progress has been made towards the realisation of the quantum internet to enable a broad range of applications that would be out of reach for classical internet. Most of these applications such as delegated quantum computation require running a secure identification protocol between a low-resource and a high-resource party to provide secure communication. Physical Unclonable Functions (PUFs) have been shown as resource-efficient hardware solutions for providing secure identification schemes in both classical and quantum settings. In this work, we propose two identification protocols based on quantum PUFs (qPUFs) as defined recently by Arapinis et al. In the first protocol, the low-resource party wishes to prove its identity to the high-resource party and in the second protocol, it is vice versa. Unlike existing identification protocols based on Quantum Read-out of PUFs which rely on the security against a specific family of attacks, our protocols provide provable exponential security against any Quantum Polynomial-Time adversary with only polynomial resource parties. We provide a comprehensive comparison between the two proposed protocols in terms of resources such as quantum memory and computing ability required in both parties as well as the communication overhead between them. A stand-out feature of our second protocol is secure identification of a high-resource party by running a purely classical verification algorithm. This is achieved by delegating quantum operations to the high-resource party and utilising the resulting classical outcomes for identification. An interesting application idea that emerges from our second protocol is certification or benchmarking of general quantum computation schemes based on purely running a classical test on the resulting measurement outcomes.