Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Algorithmica

Search In Journal Title:

Abbravation: Algorithmica

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1016/j.apcatb.2007.10.017

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

Optimal Parallel Quantum Query Algorithms

Authors: Stacey Jeffery Frederic Magniez Ronald de Wolf
Publish Date: 2016/09/08
Volume: 79, Issue: 2, Pages: 509-529
PDF Link

Abstract

We study the complexity of quantum query algorithms that make p queries in parallel in each timestep This model is in part motivated by the fact that decoherence times of qubits are typically small so it makes sense to parallelize quantum algorithms as much as possible We show tight bounds for a number of problems specifically Theta n/p2/3 pparallel queries for element distinctness and Theta n/pk/k+1 for ksum Our upper bounds are obtained by parallelized quantum walk algorithms and our lower bounds are based on a relatively small modification of the adversary lower bound method combined with recent results of Belovs et al on learning graphs We also prove some general bounds in particular that quantum and classical pparallel query complexity are polynomially related for all total functions f when p is small compared to f’s block sensitivityPartially supported by the French ANR Blanc project ANR12BS02005 RDAM a Vidi grant from the Netherlands Organization for Scientific Research NWO ERC Consolidator grant QPROGRESS the European Commission IST STREP projects Quantum Computer Science QCS 255961 Quantum Algorithms QALGO 600700 and the US ARO An extended abstract of this paper appeared in the Proceedings of the 22nd European Symposium on Algorithms ESA’14 pp 592–604The proof is a straightforward adaptation of the proof of 15 Theorem 9 but we repeat it here for completeness Let w SJSJin mathcal E p and theta SJMSJin mathcal E p Min mathcal C be an optimal solution to the primal formulation of mathrmLGCpparallel mathcal CFirst we use a variation of the adversary bound from 17 that allows the duplication of row and column indices Concretely rows and columns of Gamma are now indexed by x a and y b respectively where xin f11 yin f10 and a and b belong to some finite sets Then with slight abuse of notation Delta J is now defined such that Delta Jxayb=1 if x Jne y J and Delta Jxayb=0 otherwise Specifically in our case rows of Gamma will be indexed by x M for some xin f11 and Min mathcal C and columns will simply be indexed by yin f10Second Gamma will be the submatrix of a larger matrix widetildeGamma defined below whose rows are indexed by the elements of qntimes mathcal C and whose columns are indexed by qn Then Delta J is naturally extended to all xyin qn and Min mathcal C by tildeDelta JxMy=1 if x Jne y J and tildeDelta JxMy=0 otherwise Since Gamma circ Delta J is a submatrix of widetildeGamma circ tildeDelta J we will have Gamma circ Delta Jle widetildeGamma circ tildeDelta J Hence it suffices to upper bound the latter norm


Keywords:

References


.
Search In Abstract Of Papers:
Other Papers In This Journal:

  1. On Minimum Sum of Radii and Diameters Clustering
  2. Integer Representation and Counting in the Bit Probe Model
  3. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
  4. New Approximation Algorithms for Minimum Cycle Bases of Graphs
  5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
  6. Aligning Two Convex Figures to Minimize Area or Perimeter
  7. Introduction for S.I. AofA14
  8. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
  9. Detecting Regular Visit Patterns
  10. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  11. Random Matrices and Codes for the Erasure Channel
  12. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  13. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  14. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  15. Maximum Series-Parallel Subgraph
  16. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  17. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  18. The Parameterized Complexity of Local Search for TSP, More Refined
  19. Approximating Fixation Probabilities in the Generalized Moran Process
  20. Approximation Algorithms for Scheduling with Reservations
  21. Algorithms for the Homogeneous Set Sandwich Problem
  22. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  23. Computing Minimum Cuts by Randomized Search Heuristics
  24. Constructing Labeling Schemes through Universal Matrices
  25. An Approximation Algorithm for the Minimum Co-Path Set Problem
  26. Scheduling with an Orthogonal Resource Constraint
  27. Approximate Boyer-Moore String Matching for Small Alphabets
  28. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
  29. Between Treewidth and Clique-Width
  30. What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
  31. Multi-sided Boundary Labeling
  32. A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

Search Result: