Transcript A Computer Architecture For Quantum Programming

A Computer Architecture
For Quantum Programming
(Using QC modules in a classical computer from C++)
From: http://arxiv.org/PS_cache/cs/pdf/0103/0103009.pdf
By Tom Bersano
For EECS598 Quantum Computing
Thursday, December 13, 2001
The Goal: Quantum Programming
Classical Computer Using QC Module
Why?

A hybrid classical/quantum system can provide advantages of both
(ease of programmability/interface AND quantum speedup advantages).
Example:


Classical computer provides nice interface (data transfer, etc.) and uses
convenient compilers, etc.
Part of algorithm that would best be solved in a QC are identified, a
Quantum Circuit is compiled and implemented, and used as a ‘blackbox function call’.
Example: Grover’s Algorithm:
Find x in N … Exponential speedup over classical
Define
Quantum
Operations
Define
Q-Register
Invoke
Q-Operation
On Q-Reg
Qbitset run_Grover(bool(*f)(int), int n) {
int repetitions = sqrt(pow(2.0,n));
Qop phase_oracle(f,n);
Qop invert_zero(f_0,n);
Qop mixer = QHadamard(n);
Qop invert_mean = mixer & invert_zero & mixer;
Qop grover_step = phase_oracle & invert_mean;
Qreg input(n);
mixer(input);
for (int i=0; i<repetitions; ++i)
{
grover_step(input);
}
return input.measure();
}
Optimizations
Qreg myreg(size);
for (int i=0; i<(size-1); i++) Hadamard_2(myreg, i);
Often optimization of Q-circuit
depends on code and
equivalent circuit structure
alone, and not on register
values

Solution: Generate entire circuit
description as data structure, and
apply algebraic simplifications before
ever allocating quantum registers
size = 6
Qop circuit;
for (int i=0; i<(size-1); i++) circuit << QHadamard(2).offset(i);
Qreg myreg(size);
circuit(myreg);
Program vs. Architecture:
A Classical Computer Example
C++ code

Hardware
independent
assembly/machine
code
COMPILED
INTO

Hardware Dependent
# registers,
primitive operations,
Speed Limitations
(#cycles per instr.)
Etc.
Program vs. Architecture in QC:
The QRAM Architecture
Quantum Random Access Machine
Classical System
void main()
{
Obj n1;
…
for(…)
{
…
}
print(result);
}
Part of algorithm
that is exponential
in classical systems
Program vs. Architecture in QC:
The QRAM Architecture
Quantum Random Access Machine
Black Box QRAM:
Classical System
Memory/
Registers
(Q-Bits)
void main()
{
Obj n1;
…
CALLS
…
QC_call
RETURNS
…
print(result);
}
Encoder/
Decoder
Interface to
QRAM
ENCODES PROBLEM
READS ANSWER
Quantum Programming
Black Box QRAM:
Classical System
Memory/
Registers
(Q-Bits)
void main()
{
Obj n1;
…
CALLS
…
QC_call
RETURNS
…
print(result);
}
Compiled
Code for
Classical
Computer
Encoder/
Decoder
Interface to
QRAM
Compiler
ENCODES PROBLEM
READS ANSWER
Quantum
Circuit
Description:
Quantum Programming
Black Box QRAM:
Classical System
Memory/
Registers
(Q-Bits)
void main()
{
QReg q(5);
…
CALLS
…
QC_call
RETURNS
…
print(result);
}
Compiled
Code for
Classical
Computer
Encoder/
Decoder
Interface to
QRAM
Compiler
ENCODES PROBLEM
READS ANSWER
Quantum
Circuit
Description:
Desirable Properties
Completeness

Language maps to and from every possible Q. Circuit
Separability

QC in algorithm are always separate modules.
Classical Extension / Expressivity

Example: C++ with QC function calls
Hardware independence


C++ works on old 386, Athlon, MAC, etc.
QC extensions must work regardless of physical impl.
Quantum Programming
Data Structures:
Q.Registers:
Declaration:
Qreg a_register(5);
//allocates a register with 5 qubits
int the size = a_register.size();
//gets size of the register
Addressing:
Qreg a_qubit = a_register[3]; //selects the 4th qubit from a register
Qreg a_subreg = a_register(2,5); //selects 5 qubits starting at the 3rd one
Concatenation:
Qreg new reg = a_subreg & a_qubit; //concatenates the two registers
Resizing:
a_register += 5;
a_register -= 3;
//adds 5 qubits to my register
//drops 3 qubits from my register
Quantum Memory:
The Qreg Object
Quantum Register Management
from Classical Side: Q-Bit
Swapping
Another Advantage of Hybrid System:

Swapping bits in Quantum Registers can be difficult
and unnecessary… just use classical computation to
keep track of bit permutations for the final solution.
Quantum Operator Primitives
High Level Primitives (HLP) are implemented out of
any chosen set of Low Level Primitives (LLP) at
‘compile/run’ time.
List ctrls = (0,4,5);
List targets = (1,2,6);
Qop my op = QCnot(ctrls, targets);
Example of complete set of Quantum Low Level
Primitives:
Computational Primitives
Quantum Programming
Data Structures:
Q.Operators: (list not complete)
Application:
an_operator(a_register);
runs the circuit onto the register
Fixed arity quantum operators:
Qop my_op = QHadamard(7); Hadamard gates acting on First 7 qubits
Qop my_op = QCnot(ctrls, targets);
Controlled operators:
Qop a_controlled_op(U, 5);
creates a U conditioned by 5 qubits
Operators for classical functions:
Qop an_oracle = Qop(f,3,5); oracle for f with n = 3 and m = 5
Qop a_phase_oracle = Qop(g,4); phase oracle for g with n = 4
(m is 1)
Operators Composition:
Qop composed = part_1 & part_2; composes two Qops into a third Qop
my_operator &= an_operator; extends my operator with an operator
my_operator << an_operator; moves an operator into my operator
Quantum Operators:
The Qop object
Addition using QFt and composition
F
N4
F-1
N4+M4
Addition using QFt and composition
Qop build_three_adder(int size){
Qop phase_shifts;
for (int i=0; i<size; ++i)
phase_shifts << QCondPhase(size-i, i+1).offset(i);
Qop transform = (QFourier(size) & QSwap(size)).offset(size);
Qop adder_2 = transform & phase_shifts & (! transform);
Qop adder_3 = (adder_2 >> size);
adder_3 << adder_2.split(size, size);
return adder_3;
}
Creating Oracles/Pseudo-Classical
Operators:
Any classical non-reversible function has an equivalent
reversible function
Any reversible function can be converted efficiently into a
quantum mechanical function
Thus, in theory, we can build a quantum mechanical
oracle on a q-register for any given classical oracle
function, but we must use it appropriately to get any
speedup advantage…
My opinion: no straightforward way (yet) to build
Quantum Oracles that implement classical functions
(without being explicitly ‘called’ for each input
combination and thus losing speedup adv.)
Assumptions about Q.Hardware
Classical Case


Example: if ALU doesn’t have multiplication or
permutation, their complexity is linear in #bits
Bus size, cache size, etc. matter
Single and 2-QBit primitive gates can be
executed in constant time

For non-adjecent QBits time complexity may scale
linearly by distance (e.g., number of swaps required)
so complexity is worse than algorithmic one.
Parallel quantum execution assumed but only
exploited in homogeneous gates
Conclusions – part 1
C++ Library for Q.Programming already implemented
http://meitner.tn.infn.it/~bettelli/qcomp/qlang/index.pl
QC hardware not ready, can work with simulator for the moment.
Accomplishment:


Allows rewriting algorithms in formal language
Provides a general Framework for:
Comparing/Testing different implementations/algorithms for:




high level simplification and optimization routines for quantum circuits
schemes for high level to low level and hardware independent to dependent
translation routines for quantum circuits
hardware architectures for the execution of quantum code (with timing
simulations);
robustness of error correction codes and fault tolerant quantum computation with
respect to generic error models
Algorithm design:
having an high level interface for the specification of algorithms which are to be
fed into quantum simulators;
quantum programming (when quantum computers will be ready)

Conclusions – part 2
Weaknesses


Says that quantum circuit optimizations can
be done but doesn’t tell you how to do them
Says that pseudo-classical oracles can in
theory be created but doesn’t tell you how to
do so