Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0611033 · AIP conference proceedings

Approximate Randomization of Quantum States With Fewer Bits of Key

Paul A. Dickinson, Ashwin Nayak

Published Jan 1, 2006• 32 citations
arXivHTMLPDF

Abstract

Randomization of quantum states is the quantum analogue of the classical one‐time pad. We present an improved, efficient construction of an approximately randomizing map that uses O(d/ε2) Pauli operators to map any d‐dimensional state to a state that is within trace distance ε of the completely mixed state. Our bound is a log d factor smaller than that of Hayden, Leung, Shor, and Winter, and Ambainis and Smith.Then, we show that a random sequence of essentially the same number of unitary operators, chosen from an appropriate set, with high probability form an approximately randomizing map for d‐dimensional states. Finally, we discuss the optimality of these schemes via connections to different notions of pseudorandomness, and give a new lower bound for small ε.

DOI
10.1063/1.2400876

Related papers

On Almost Randomizing Channels with a Short

Kraus Decomposition, Guillaume Aubrun

For large d, we study quantum channels on C d obtained by selecting ran- domly N independent Kraus operators according to a probability measure µ on the unitary group U(d). When µ is the Haar measure, we show that for N d/e 2 , such a channel is e-randomizing with high probability, which means that it maps every state within distance e/d (in operator norm) of the maximally mixed state. This slightly improves on a result by Hayden, Leung, Shor and Winter by optimizing their discreti- zation argument. Moreover, for general µ, we obtain an e-randomizing channel provided N d (log d) 6 /e 2 .F ord = 2 k (k qubits), this includes Kraus operators obtained by ten- soring k random Pauli matrices. This leads to more efficient constructions of almost randomizing channels. The proof uses recent results on empirical processes in Banach spaces.

•Jan 1, 2009•0 citations

A remark on the paper ``Randomizing quantum states: Constructions and applications''

Guillaume Aubrun

The concept of $\e$-randomizing quantum channels has been introduced by Hayden, Leung, Shor and Winter in connection with approximately encrypting quantum states. They proved using a discretization argument that sets of roughly $d \log d$ random unitary operators provide examples of such channels on $\C^d$. We show that a simple trick improves the efficiency of the argument and reduces the number of unitary operators to roughly $d$.

arXiv:0802.4193•Feb 28, 2008•1 citation

Approximate Private Quantum Channels

Dickinson, Paul

This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for $ε$-randomizing maps, $n+2\log(1/ε)+c$ bits required to $ε$-randomize an arbitrary $n$-qubit state by improving a scheme of Ambainis and Smith \cite{AS04} based on small bias spaces \cite{NN90, AGHP92}. We show by a probabilistic argument that in fact the great majority of random schemes using slightly more than this many bits of key are also $ε$-randomizing. We provide the first known non-trivial lower bound for $ε$-randomizing maps, and develop several conditions on them which we hope may be useful in proving stronger lower bounds in the future.

arXiv:quant-ph/0611037•Nov 2, 2006•0 citations

Approximate quantum encryption with even shorter keys

Temel, Mehmet, Boris Škorić

Perfect encryption of a qubit state using the Quantum One-Time Pad (QOTP) requires 2 classical key bits. More generally, perfect QOTP encryption of a $2^n$-dimensional state requires $2n$ classical bits. However, almost-perfect encryption, with information-theoretic security, can be achieved with only little more than $1$ key bit per qubit. In this paper we slightly improve the key length. We show that key length $n+\frac23\log\frac1\varepsilon$ suffices to encrypt $n$ qubits in such a way that the cipherstate has trace distance $\leq\varepsilon$ from the fully mixed state. The previous best result was $n+2\log\frac1\varepsilon$. Similar to the previous literature, we expand the key to a $2n$-bit pseudorandom string which is then used as a QOTP key. In this expansion we make use of $2n$ bits of public randomness which are included as a classical part of the cipherstate. Our key expansion is slightly faster than in previous works.

•Jan 1, 2022•1 citation

Randomized Algorithms and Lower Bounds for Quantum Simulation

Zhang, Chi

We consider deterministic and {\em randomized} quantum algorithms simulating $e^{-iHt}$ by a product of unitary operators $e^{-iA_jt_j}$, $j=1,...,N$, where $A_j\in\{H_1,...,H_m\}$, $H=\sum_{i=1}^m H_i$ and $t_j > 0$ for every $j$. Randomized algorithms are algorithms approximating the final state of the system by a mixed quantum state. First, we provide a scheme to bound the trace distance of the final quantum states of randomized algorithms. Then, we show some randomized algorithms, which have the same efficiency as certain deterministic algorithms, but are less complicated than their opponentes. Moreover, we prove that both deterministic and randomized algorithms simulating $e^{-iHt}$ with error $\e$ at least have $Ω(t^{3/2}\e^{-1/2})$ exponentials.

arXiv:0910.4145•Oct 21, 2009•1 citation

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

David Jennings, Matteo Lostaglio, Sam Pallister +2 more

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.

arXiv:2305.11352•PRX Quantum•Oct 7, 2025•6 citations
Randomization of quantum states is the quantum analogue of the classical one‐time pad. We present an improved, efficient construction of an approximately randomizing map that uses O(d/ε2) Pauli operators to map any d‐dimensional state to a state that is within trace distance ε of the completely mixed state. Our bound is a log d factor smaller than that of Hayden, Leung, Shor, and Winter, and Ambainis and Smith.Then, we show that a random sequence of essentially the same number of unitary operators, chosen from an appropriate set, with high probability form an approximately randomizing map for d‐dimensional states. Finally, we discuss the optimality of these schemes via connections to different notions of pseudorandomness, and give a new lower bound for small ε.
For large d, we study quantum channels on C d obtained by selecting ran- domly N independent Kraus operators according to a probability measure µ on the unitary group U(d). When µ is the Haar measure, we show that for N d/e 2 , such a channel is e-randomizing with high probability, which means that it maps every state within distance e/d (in operator norm) of the maximally mixed state. This slightly improves on a result by Hayden, Leung, Shor and Winter by optimizing their discreti- zation argument. Moreover, for general µ, we obtain an e-randomizing channel provided N d (log d) 6 /e 2 .F ord = 2 k (k qubits), this includes Kraus operators obtained by ten- soring k random Pauli matrices. This leads to more efficient constructions of almost randomizing channels. The proof uses recent results on empirical processes in Banach spaces.
The concept of $\e$-randomizing quantum channels has been introduced by Hayden, Leung, Shor and Winter in connection with approximately encrypting quantum states. They proved using a discretization argument that sets of roughly dlog⁡dd \log ddlogd random unitary operators provide examples of such channels on $\C^d$. We show that a simple trick improves the efficiency of the argument and reduces the number of unitary operators to roughly ddd.
This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for εεε-randomizing maps, n+2log⁡(1/ε)+cn+2\log(1/ε)+cn+2log(1/ε)+c bits required to εεε-randomize an arbitrary nnn-qubit state by improving a scheme of Ambainis and Smith \cite{AS04} based on small bias spaces \cite{NN90, AGHP92}. We show by a probabilistic argument that in fact the great majority of random schemes using slightly more than this many bits of key are also εεε-randomizing. We provide the first known non-trivial lower bound for εεε-randomizing maps, and develop several conditions on them which we hope may be useful in proving stronger lower bounds in the future.
Perfect encryption of a qubit state using the Quantum One-Time Pad (QOTP) requires 2 classical key bits. More generally, perfect QOTP encryption of a 2n2^n2n-dimensional state requires 2n2n2n classical bits. However, almost-perfect encryption, with information-theoretic security, can be achieved with only little more than 111 key bit per qubit. In this paper we slightly improve the key length. We show that key length n+23log⁡1εn+\frac23\log\frac1\varepsilonn+32​logε1​ suffices to encrypt nnn qubits in such a way that the cipherstate has trace distance ≤ε\leq\varepsilon≤ε from the fully mixed state. The previous best result was n+2log⁡1εn+2\log\frac1\varepsilonn+2logε1​. Similar to the previous literature, we expand the key to a 2n2n2n-bit pseudorandom string which is then used as a QOTP key. In this expansion we make use of 2n2n2n bits of public randomness which are included as a classical part of the cipherstate. Our key expansion is slightly faster than in previous works.
We consider deterministic and {\em randomized} quantum algorithms simulating e−iHte^{-iHt}e−iHt by a product of unitary operators e−iAjtje^{-iA_jt_j}e−iAj​tj​, j=1,...,Nj=1,...,Nj=1,...,N, where Aj∈{H1,...,Hm}A_j\in\{H_1,...,H_m\}Aj​∈{H1​,...,Hm​}, H=∑i=1mHiH=\sum_{i=1}^m H_iH=∑i=1m​Hi​ and tj>0t_j > 0tj​>0 for every jjj. Randomized algorithms are algorithms approximating the final state of the system by a mixed quantum state. First, we provide a scheme to bound the trace distance of the final quantum states of randomized algorithms. Then, we show some randomized algorithms, which have the same efficiency as certain deterministic algorithms, but are less complicated than their opponentes. Moreover, we prove that both deterministic and randomized algorithms simulating e−iHte^{-iHt}e−iHt with error $\e$ at least have $Ω(t^{3/2}\e^{-1/2})$ exponentials.
Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.