To understand quantum gate array complexity, we define a problem named exact non-identity check, which is a decision problem to determine whether a given classical description of a quantum circuit is strictly equivalent to the identity or not. We show that the computational complexity of this problem is non-deterministic quantum polynomial-time (NQP)-complete. As corollaries, it is derived that exact non-equivalence check of two given classical descriptions of quantum circuits is also NQP-complete and that minimizing the number of quantum gates for a given quantum circuit without changing the implemented unitary operation is NQP-hard.
Program obfuscation aims to hide the inner workings of a program while preserving its functionality. In the quantum setting, recent works have obtained obfuscation schemes for specialized classes of quantum circuits. For instance, Bartusek, Brakerski, and Vaikuntanathan (STOC 2024) constructed a quantum state obfuscation scheme, which supports the obfuscation of quantum programs represented as quantum states for pseudo-deterministic quantum programs with classical inputs and outputs in the classical oracle model. In this work, we improve upon existing results by constructing the first quantum state obfuscation scheme for unitary (or approximately unitary) quantum programs supporting quantum inputs and outputs in the classical oracle model. At the core of our obfuscation scheme are two novel ingredients: a functional quantum authentication scheme that allows key holders to learn specific functions of the authenticated quantum state with simulationbased security, and a compiler that represents an arbitrary quantum circuit as a projective linear-plus-measurement quantum program described by a sequence of non-adaptive Clifford gates interleaved with adaptive and compatible measurements.
The advent of a full-scale quantum computer will severely impact most currently-used cryptographic systems. The most well-known aspect of this impact lies in the computational-hardness assumptions that underpin the security of most current public-key cryptographic systems: a quantum computer can factor integers and compute discrete logarithms in polynomial time, thereby breaking systems based on these problems. However, simply replacing these problems by other which are (believed to be) impervious even to a quantum computer does not completely solve the issue. Indeed, many security proofs of cryptographic systems are no longer valid in the presence of a quantum-capable attacker; while this does not automatically implies that the affected systems would be broken by a quantum computer, it does raises questions on the exact security guarantees that they can provide. This overview document aims to analyze all aspects of the impact of quantum computers on cryptographic, by providing an overview of current quantum-hard computational problems (and cryptographic systems based on them), and by presenting the security proofs that are affected by quantum-attackers, detailing what is the current status of research on the topic and what the expected effects on security are.
In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit
C, of the classical task of producing a description of the unitary obtained by conjugating a Pauli
P (corresponding to a Bell-measurement outcome) by
C, where this description only depends on the input-output functionality of
CPC†. The task above, in turn, is at least as hard as the problem of determining whether two
n-qubit quantum circuits are perfectly equivalent up to global phase. In 2009, Tanaka defined the corresponding decision problem Exact Non-Identity Check (ENIC) and showed that ENIC is NQP-complete and thus NP-hard as well. Motivated by the 2021 protocol, we consider in this work what happens when we pass from low T-count to low T-depth. We show that, for Clifford+T-circuits of T-depth
O(log(n)), deciding ENIC remains NP-hard. In particular, we show this by relating certain decision problems on Pauli coefficients of Clifford+T unitaries to well-known hardness results for codeword weights in binary linear codes. This effectively rules out the possibility, for Clifford+T-circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation based computational indistinguishability obfuscation, unless P=NP. It also provides a new, independent proof of the hardness of ENIC, even at low T-depth. Along the way, we prove the NP-hardness of some related circuit problems.
A quantum public-key encryption scheme is presented in this paper. In the proposed scheme, ciphertext is described by quantum states and security of this scheme is based on the assumption that NP-complete (NP-C) problems are intractable against quantum (probabilistic) polynomial-time Turing machines (QPTM). One of the main properties of our scheme is that it is immune to off-line attack, in which the adversaries can copy all the ciphertext on channel and analyze them at a later time. We call this type of encryption scheme the computationally secure uncloneable encryption scheme. It is shown that the presented scheme can also be used to encrypt quantum states.
Homomorphic encryption enables computation on encrypted data while maintaining secrecy. This leads to an important open question whether quantum computation can be delegated and verified in a non-interactive manner or not. In this paper, we affirmatively answer this question by constructing the quantum homomorphic encryption scheme with quantum obfuscation. It takes advantage of the interchangeability of the unitary operator, and exchanges the evaluation operator and the encryption operator by means of equivalent multiplication to complete homomorphic encryption. The correctness of the proposed scheme is proved theoretically. The evaluator does not know the decryption key and does not require a regular interaction with a user. Because of key transmission after quantum obfuscation, the encrypting party and the decrypting party can be different users. The output state has the property of complete mixture, which guarantees the scheme security. Moreover, the security level of the quantum homomorphic encryption scheme depends on quantum obfuscation and encryption operators.