Quantum algorithms for distinguishing unitary operators

Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$ -qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

arXiv:2402.14803Feb 22, 20242 citations

Quantum certification of state set and unitary channel

Wei Dong Xie

We study efficient quantum certification algorithms for quantum state set and unitary quantum channel. We present an algorithm that uses $O(\varepsilon^{-4}\ln |\mathcal{P}|)$ copies of an unknown state to distinguish whether the unknown state is contained in or $\varepsilon$ -far from a finite set $\mathcal{P}$ of known states with respect to the trace distance. This algorithm is more sample-efficient in some settings. Previous study showed that one can distinguish whether an unknown unitary $U$ is equal to or $\varepsilon$ -far from a known or unknown unitary $V$ in fixed dimension with $O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and thus an ancilla system is needed. We give an algorithm that distinguishes the two cases with $O(\varepsilon^{-1})$ uses of the unitary, using much fewer or no ancilla compared with previous results.We study efficient quantum certification algorithms for quantum state set and unitary quantum channel. We present an algorithm that uses $O(\varepsilon^{-4}\ln |\mathcal{P}|)$ copies of an unknown state to distinguish whether the unknown state is contained in or $\varepsilon$-far from a finite set $\mathcal{P}$ of known states with respect to the trace distance. This algorithm is more sample-efficient in some settings. Previous study showed that one can distinguish whether an unknown unitary $U$ is equal to or $\varepsilon$-far from a known or unknown unitary $V$ in fixed dimension with $O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and thus an ancilla system is needed. We give an algorithm that distinguishes the two cases with $O(\varepsilon^{-1})$ uses of the unitary, using much fewer or no ancilla compared with previous results.

arXiv:2103.02837Mar 4, 20210 citations

UNITARY OPERATORS IN QUANTUM THEORY

IMPERIAL COLLEGE PRESS eBooksSep 1, 19950 citations

Quantum Query Complexity of Unitary Operator Discrimination

Akinori Kawachi, Kenichi Kawano, François Le Gall +1 more

Lecture notes in computer scienceJan 1, 20174 citations

Ancilla-free certification of unitary quantum processes

Wei Xie

We study efficient quantum certification algorithms for unitary quantum process using no ancilla. Previous study showed that one can distinguish whether an unknown unitary $U$ is equal to or $\varepsilon$ -far from a known or unknown unitary $V$ in fixed dimension with $O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and thus a high dimensional ancilla system is always needed. We give an algorithm that distinguishes the two cases with $O(\varepsilon^{-1})$ uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.We study efficient quantum certification algorithms for unitary quantum process using no ancilla. Previous study showed that one can distinguish whether an unknown unitary $U$ is equal to or $\varepsilon$-far from a known or unknown unitary $V$ in fixed dimension with $O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and thus a high dimensional ancilla system is always needed. We give an algorithm that distinguishes the two cases with $O(\varepsilon^{-1})$ uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.

arXiv:2211.15647Nov 28, 20220 citations

U^{\otimes \mathrm{poly}(n)}

can distinguish whether an

n

-qubit unitary

U

was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

We study efficient quantum certification algorithms for quantum state set and unitary quantum channel. We present an algorithm that uses

O(\varepsilon^{-4}\ln |\mathcal{P}|)

copies of an unknown state to distinguish whether the unknown state is contained in or

\varepsilon

-far from a finite set

\mathcal{P}

of known states with respect to the trace distance. This algorithm is more sample-efficient in some settings. Previous study showed that one can distinguish whether an unknown unitary

U

is equal to or

\varepsilon

-far from a known or unknown unitary

V

in fixed dimension with

O(\varepsilon^{-2})

uses of the unitary, in which the Choi state is used and thus an ancilla system is needed. We give an algorithm that distinguishes the two cases with

O(\varepsilon^{-1})

uses of the unitary, using much fewer or no ancilla compared with previous results.

We study efficient quantum certification algorithms for unitary quantum process using no ancilla. Previous study showed that one can distinguish whether an unknown unitary

U

is equal to or

\varepsilon

-far from a known or unknown unitary

V

in fixed dimension with

O(\varepsilon^{-2})

uses of the unitary, in which the Choi state is used and thus a high dimensional ancilla system is always needed. We give an algorithm that distinguishes the two cases with

O(\varepsilon^{-1})

uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.