Name
Abstract | ||
|---|---|---|
We investigate the theoretical limits of the effect of the quantum interaction distance on the speed of exact quantum addition circuits. For this study, we exploit graph embedding for quantum circuit analysis. We study a logical mapping of qubits and gates of any Ω(log n)-depth quantum adder circuit for two n-qubit registers onto a practical architecture, which limits interaction distance to the nearest neighbors only and supports only one- and two-qubit logical gates. Unfortunately, on the chosen k-dimensional practical architecture, we prove that the depth lower bound of any exact quantum addition circuits is no longer Ω(log n), but Ω(k√n). This result, the first application of graph embedding to quantum circuits and devices, provides a new tool for compiler development, emphasizes the impact of quantum computer architecture on performance, and acts as a cautionary note when evaluating the time performance of quantum algorithms. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2000502.2000504 | ACM Journal on Emerging Technologies in Computing Systems (JETC) |
Keywords | Field | DocType |
quantum circuit analysis,quantum computer architecture,emphasizes the impact of quantum computer architec- ture,provides a new tool for compiler development,quantum interaction distance,interaction,interaction distance,exact quantum addition circuit,log n,practical architecture,quantum addition circuits,k-dimensional practical architecture,quantum adder,depth lower bound,and acts as a cautionary note when evaluating the time performance of quantum algorithms. keywords: quantum architecture,first application of graph embedding to quantum circuits and devices,depth quantum adder circuit,quantum algorithm,hardware architecture,quantum physics,lower bound,quantum computer,graph embedding,nearest neighbor,logic gate | Topology,Computer science,Quantum computer,Electronic engineering,Theoretical computer science,Quantum simulator,Quantum algorithm,Quantum information,Quantum operation,Quantum capacity,Quantum error correction,Quantum network | Journal |
Volume | Issue | ISSN |
7 | 3 | 1550-4832 |
Citations | PageRank | References |
16 | 0.97 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Byung-Soo Choi | 1 | 46 | 7.09 |
| Rodney Van Meter | 2 | 366 | 36.33 |