We study the class of discrete Wigner functions proposed by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to describe quantum states using a discrete phase space based on finite fields. We find the extrema of such ...
详细信息
We study the class of discrete Wigner functions proposed by Gibbons et al. [Phys. Rev. A 70, 062101 (2004)] to describe quantum states using a discrete phase space based on finite fields. We find the extrema of such functions for small Hilbert-space dimensions and present a quantum-information application: a construction of quantum random-access codes. These are constructed using the complete set of phase-space point operators to find encoding states and to obtain the codes’ average success rates for Hilbert-space dimensions 2, 3, 4, 5, 7, and 8.
A grid polygon is a polygon whose vertices are points of a grid. We define an injective map between permutations of length n and a subset of grid polygons on n vertices, which we call consecutive-minima polygons. By t...
详细信息
A grid polygon is a polygon whose vertices are points of a grid. We define an injective map between permutations of length n and a subset of grid polygons on n vertices, which we call consecutive-minima polygons. By the kernel method, we enumerate sets of permutations whose consecutive-minima polygons satisfy specific geometric conditions. We deal with 2-variate and 3-variate generating functions.
A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions...
详细信息
A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t. We then show that an approximate 4-design provides a derandomization of the statedistinction problem considered by Sen (quant-ph/0512085), which is relevant to solving certain instances of the hidden subgroup problem.
For any AND-OR formula of size N, there exists a bounded-error N 1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximate...
详细信息
For any AND-OR formula of size N, there exists a bounded-error N 1/2+o(1) -time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximat...
详细信息
For any AND-OR formula of size N, there exists a bounded-error N 1/2+o(1) -time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algo...
详细信息
Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and op...
详细信息
ISBN:
(纸本)1595931341
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal. Copyright 2006 ACM.
The successful application to elliptic curve cryptography of side-channel attacks, in which information about the secret key can be recovered from the observation of side channels like power consumption, timing, or el...
详细信息
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 ...
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 ***, 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 ε.
暂无评论