Name
Abstract | ||
|---|---|---|
We study the complexity of some computational problems on finite black-box rings whose elements are encoded as strings of a given length and the ring operations are performed by a black-box oracle. We give a polynomial-time quantum algorithm to compute a basis representation for a given black-box ring. Using this result we obtain polynomial-time quantum algorithms for several natural computational problems over black-box rings. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11809678_15 | COCOON |
Keywords | Field | DocType |
computational problem,black-box oracle,polynomial-time quantum algorithm,finite black-box ring,natural computational problem,black-box ring,ring operation,basis representation,black-box ring problem,quantum algorithm,polynomial time,natural computing | Quantum complexity theory,Asymptotic computational complexity,Discrete mathematics,Computational problem,Combinatorics,Polynomial ring,Computer science,Quantum computer,Quantum algorithm,Time complexity,Computational resource | Conference |
Volume | ISSN | ISBN |
4112 | 0302-9743 | 3-540-36925-2 |
Citations | PageRank | References |
2 | 0.45 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Bireswar Das | 2 | 66 | 10.61 |
| Partha Mukhopadhyay | 3 | 91 | 12.71 |