2012

Efficient Distributed Quantum Computing

Beals, Robert, Brierley, Stephen, Gray, Oliver et al.

Understand

We provide algorithms for efficiently addressing quantum memory in parallel.

These imply that the standard circuit model can be simulated with low overhead by the more realistic model of a distributed quantum computer.
As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit.
In addition, we apply our results to existing memory intensive quantum algorithms.

Built on

W. Feller, An Introduction to Probability Theory and its Applications, Vol 1
1950
Earlier work this paper cites.
M. Ajtai, J. Komlos, and E. Szemeredi, An O ⁡ ( n log ⁡ n ) O(n\log n)
1983
Earlier work this paper cites.
L. G. Valiant. Optimally Universal Parallel Computers
1988
Earlier work this paper cites.
M. Paterson, Improved Sorting Networks with O ⁡ ( log ⁡ N ) O(\log N) Depth
1990
Earlier work this paper cites.
L. G. Valiant. A bridging model for parallel computation
1990
Earlier work this paper cites.
F.T. Leighton, Introduction to parallel algorithms and architectures
1992
Earlier work this paper cites.
D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, Limitations of noisy reversible computation,
1996
Earlier work this paper cites.
L. Grover, A fast quantum mechanical algorithm for database search
1996
Earlier work this paper cites.
G. Brassard and P. Hoyer, An exact quantum mechanical polynomial time algorithm for Simon’s problem
1997
Earlier work this paper cites.
G. Brassard, P. Hoyer, and A. Tapp, Cryptology Column - Quantum algorithm for the Collision problem
1997
Earlier work this paper cites.
J. Cirac, P. Zoller, H. Kimble, and H. Mabuchi, Quantum State Transfer and Entanglement Distribution among Distant Nodes in a Quantum Network
1997
Earlier work this paper cites.
R. Cleve and H. Buhrman, Substituting quantum entanglement for communication
1997
Earlier work this paper cites.
A. Kitaev, Quantum computations: algorithms and error correction,
1997
Earlier work this paper cites.

Similar

D. Knuth, The art of computer programming: volume 3
1998
Cited alongside, same era.
C. Zalka, Could Grover’s algorithm help in searching an actual database?
1999
Cited alongside, same era.
G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation
2000
Cited alongside, same era.
N. Cerf, L. Grover, and C. Williams, Nested quantum search and NP-hard problems
2000
Cited alongside, same era.
M. Nielsen and I. Chuang, Quantum computation and Quantum Information
2000
Cited alongside, same era.
H. Ramesh and V. Vinay, String matching in O ~ ( n + m ) \tilde{O}(\sqrt{n}+\sqrt{m}) quantum time
2003
Cited alongside, same era.
A. Ambainis, Quantum Search Algorithms
2004
Cited alongside, same era.
A. Blais, R.-S. Huang, A. Wallraff, S. Girvin, and R. Schoelkopf, Cavity quantum electrodynamics for superconducting electrical circuits: An architecture for quantum computation
2004
Cited alongside, same era.
L. Grover and T. Rudolph, How significant are the known Collision and Element Distinctness quantum algorithms?
2004
Cited alongside, same era.
A. Wallraff, D. Schuster, A. Blais, L. Frunzio, R.-S. Huang, J. Majer, S. Kumar, S. Girvin, and R. Schoelkopf, Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics
2004
Cited alongside, same era.
H. Buhrman, C. Durr, M. Heiligman, P. Hoyer, F. Magniez, M. Santha, and R. de Wolf, Quantum Algorithms for Element Distinctness
2005
Cited alongside, same era.
R. Van Meter and M Oskin, Architectural implications of quantum computing technologies
2006
Cited alongside, same era.

Then

F. Magniez, M. Santha and M. Szegedy, Quantum algorithms for the triangle finding problem
2007
Later among the works it cites.
V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory
2008
Later among the works it cites.
V. Giovannetti, S. Lloyd, and L. Maccone, Architectures for a quantum random access memory
Original
2008
Later among the works it cites.
D. J. Bernstein, Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?
2009
Later among the works it cites.
R. Van Meter, W. Munro, K. Nemoto and K. Itoh, Arithmetic on a distributed-memory quantum multicomputer
2009
Later among the works it cites.
H. Thapliyal, N. Ranganathan, and R. Ferreira, Design of a Comparator Tree Based on Reversible Logic
2010
Later among the works it cites.
R. Van Meter, T.Ladd, A. Fowler and Y. Yamamoto, Distributed quantum computation architecture using semiconductor nanophotonics,
Original
2010
Later among the works it cites.
B.-S. Choi and R. Van Meter On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
Original
2011
Later among the works it cites.
Y Hirata, M Nakanishi, S Yamashita and Y Nakashima An efficient conversion of quantum circuits to a linear nearest neighbor architecture
2011
Later among the works it cites.
A. Belovs, Span Programs for Functions with Constant-Sized 1-certificates
Original
2012
Closest in time.
N. Jones, R. Van Meter, A. Fowler, P. McMahon, J. Kim, T. Ladd and Y. Yamamoto Layered architecture for quantum computing,
Original
2012
Closest in time.
S. Ritter, C. Nölleke, C. Hahn, A. Reiserer, A. Neuzner, M. Uphoff, M. Mücke, E. Figueroa, J. Bochmann, and G. Rempe, An elementary quantum network of single atoms in optical cavities
Original
2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…