An Investigation into the Realities of a Quantum Datapath

Nemanja Isailovic

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2010-60

May 11, 2010

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-60.pdf

Quantum computing has shown great potential for being able to solve certain problems which are intractable on classical machines. Peter Shor devised a means to factor large number in polynomial time on a quantum machine, a feat which would compromise modern public key cryptosystems. Further, simulation of quantum mechanical systems, which is exponential in both space and time on a classical machine, is expected to be far faster on a quantum machine. In this work, we present mechanisms for producing a laid out and scheduled quantum datapath tailored to a particular target circuit.

We identify two key pieces of support infrastructure in a quantum datapath. First, some quantum operations require the use of helper qubits known as ancilla qubits which are not part of the target circuit specification. We introduce and design efficient ancilla factories to use as basic functional units in our datapath layouts. Second, we provide designs for the basic components that allow the construction of a teleportation network, which is necessary for long distance communication on a quantum datapath.

We utilize our basic component designs in proposing a malleable architectural specification which we call Qalypso. The benefit of the flexibility of Qalypso lies in the ability to fine tune the various components of the datapath to suit the needs of a given quantum circuit. Ancilla bandwidth, network resources and interfacing of support infrastructure to data may all be tailored to fit circuit characteristics.

To complete the process of laying out and scheduling a quantum circuit, we device heuristics for mapping the circuit onto Qalypso while simultaneously finalizing the datapath characteristics as appropriate for the circuit. Our methods produce a final realizable datapath layout and associated scheduling, both optimized for the circuit in question.

We have implemented these heuristics in a quantum CAD flow toolset currently tailored to designing architectures in ion trap technology. We conclude this thesis by demonstrating the application of these heuristics through the automated toolset to construct a datapath and schedule optimized for Shor’s factorization algorithm.

Advisors: John D. Kubiatowicz

BibTeX citation:

@phdthesis{Isailovic:EECS-2010-60,
    Author= {Isailovic, Nemanja},
    Title= {An Investigation into the Realities of a Quantum Datapath},
    School= {EECS Department, University of California, Berkeley},
    Year= {2010},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-60.html},
    Number= {UCB/EECS-2010-60},
    Abstract= {Quantum computing has shown great potential for being able to solve certain problems which are intractable on classical machines. Peter Shor devised a means to factor large number in polynomial time on a quantum machine, a feat which would compromise modern public key cryptosystems. Further, simulation of quantum mechanical systems, which is exponential in both space and time on a classical machine, is expected to be far faster on a quantum machine. In this work, we present mechanisms for producing a laid out and scheduled quantum datapath tailored to a particular target circuit.

We identify two key pieces of support infrastructure in a quantum datapath. First, some quantum operations require the use of helper qubits known as ancilla qubits which are not part of the target circuit specification. We introduce and design efficient ancilla factories to use as basic functional units in our datapath layouts. Second, we provide designs for the basic components that allow the construction of a teleportation network, which is necessary for long distance communication on a quantum datapath.

We utilize our basic component designs in proposing a malleable architectural specification which we call Qalypso. The benefit of the flexibility of Qalypso lies in the ability to fine tune the various components of the datapath to suit the needs of a given quantum circuit.  Ancilla bandwidth, network resources and interfacing of support infrastructure to data may all be tailored to fit circuit characteristics.

To complete the process of laying out and scheduling a quantum circuit, we device heuristics for mapping the circuit onto Qalypso while simultaneously finalizing the datapath characteristics as appropriate for the circuit. Our methods produce a final realizable datapath layout and associated scheduling, both optimized for the circuit
in question.

We have implemented these heuristics in a quantum CAD flow toolset currently tailored to designing architectures in ion trap technology. We conclude this thesis by demonstrating the application of these heuristics through the automated toolset to construct a datapath and schedule optimized for Shor’s factorization algorithm.},
}

EndNote citation:

%0 Thesis
%A Isailovic, Nemanja 
%T An Investigation into the Realities of a Quantum Datapath
%I EECS Department, University of California, Berkeley
%D 2010
%8 May 11
%@ UCB/EECS-2010-60
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-60.html
%F Isailovic:EECS-2010-60