NDLI: On the impossibility of a quantum sieve algorithm for graph isomorphism

Please wait, while we are loading the content...

Statistically-hiding commitment from any one-way function

Voronoi diagrams in n · 2o(√lg lg n) time

Faster integer multiplication

Smooth sensitivity and sampling in private data analysis

How to rank with few errors

On the submodularity of influence in social networks

Hardness of routing with congestion in directed graphs

Iteratively constructing preconditioners via the conjugate gradient method

Distributed computing theory: algorithms, impossibility results, models, and proofs

The condition number of a randomly perturbed matrix

Circuit lower bounds for Merlin-Arthur classes

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Linear probing with constant independence

Limitations of VCG-based mechanisms

Interval completion with few edges

Parallel repetition: simplifications and the no-signaling case

Randomly coloring planar graphs with fewer colors than the maximum degree

Property testing in hypergraphs and the removal lemma

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Playing games with approximation algorithms

Toward a general theory of quantum games

All-pairs bottleneck paths for general graphs in truly sub-cubic time

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

Survivable network design with degree or order constraints

Lower bounds for randomized read/write stream algorithms

On achieving the "best of both worlds" in secure multiparty computation

Lower bounds for 2-dimensional range counting

Fourier meets möbius: fast subset convolution

The price of privacy and the limits of LP decoding

Approximation algorithms for budgeted learning problems

First to market is not everything: an analysis of preferential attachment with fitness

Polynomial flow-cut gaps and hardness of directed cut problems

On the convergence of Newton's method for monotone systems of polynomial equations

Balanced allocations: the weighted case

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Optimal suffix selection

The communication complexity of uncoupled nash equilibrium procedures

Computing crossing number in linear time

An efficient parallel repetition theorem for Arthur-Merlin games

Inapproximability of the Tutte polynomial

Testing k-wise and almost k-wise independence

Negative weights make adversaries stronger

Reordering buffers for general metric spaces

Search via quantum walk

More algorithms for all-pairs shortest paths in weighted graphs

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Approximating minimum bounded degree spanning trees to within one of optimal

Lower bounds in communication complexity based on factorization norms

Zero-knowledge from secure multiparty computation

Combinatorial complexity in O-minimal geometry

An approximation algorithm for max-min fair allocation of indivisible goods

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Balanced max 2-sat might not be the hardest

A combinatorial, primal-dual approach to semidefinite programs

Towards 3-query locally decodable codes of subexponential length

Separating $AC^{0}$ from depth-2 majority circuits

Proportional response dynamics leads to market equilibrium

Terminal backup, 3D matching, and covering cubic graphs

Low-end uniform hardness vs. randomness tradeoffs for AM

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Low-degree tests at large distances

On the impossibility of a quantum sieve algorithm for graph isomorphism

Some new results on node-capacitated packing of A-paths

Local embeddings of metric spaces

Improved approximation for directed cut problems

Constructing non-computable Julia sets

Simple deterministic approximation algorithms for counting matchings

Tight bounds for asynchronous randomized consensus

A 3-query PCP over integers

One sketch for all: fast algorithms for compressed sensing

Eisenberg-Gale markets: algorithms and structural properties

Holographic algorithms: from art to science

Verifying and decoding in constant depth

Lattices that admit logarithmic worst-case to average-case connection factors

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

Sampling-based dimension reduction for subspace approximation

Degree-constrained network flows

On the impossibility of a quantum sieve algorithm for graph isomorphism

Content Provider	ACM Digital Library
Author	Sniady, Piotr Russell, Alexander Moore, Cristopher
Abstract	It is known that any quantum algorithm for Graph Isomorphism thatworks within the framework of the hidden subgroup problem (HSP) must performhighly entangled measurements across Ω(n log n) coset states. One ofthe only known models for how such a measurement could be carried outefficiently is Kuperberg's algorithm for the HSP in the dihedral group, in whichquantum states are adaptively combined and measured according to thedecomposition of tensor products into irreducible representations. This "quantum sieve" starts with coset states, and works its way down towardsrepresentations whose probabilities differ depending on, for example, whetherthe hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for Graph Isomorphism. Specifically, we consider the natural reduction of Graph Isomorphism to the HSP over the the wreath product $S_{n}$ ࣀ $Z_{2}.$ Using a recently proved bound on the irreducible characters of $S_{n},$ we show that no algorithm in this family can solve Graph Isomorphism in less than $e^{Ω(√n)}$ time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time eO(√(n log n)).
Starting Page	536
Ending Page	545
Page Count	10
File Format	PDF
ISBN	9781595936318
DOI	10.1145/1250790.1250868
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Quantum computation Graph isomorphism problem
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in