A flexible representation of quantum images for po

QuantumInfProcess(2011)10:63–84DOI10.1007/s11128-010-0177-yAflexiblerepresentationofquantumimagesforpolynomialpreparation,imagecompression,andprocessingoperationsPhucQ.Le·FangyanDong·KaoruHirotaReceived:12October2009/Accepted:5April2010/Publishedonline:17April2010©SpringerScience+BusinessMedia,LLC2010AbstractAFlexibleRepresentationofQuantumImages(FRQI)isproposedtopro-videarepresentationforimagesonquantumcomputersintheformofanormalizedstatewhichcapturesinformationaboutcolorsandtheircorrespondingpositionsintheimages.AconstructivepolynomialpreparationfortheFRQIstatefromaninitialstate,analgorithmforquantumimagecompression(QIC),andprocessingoperationsforquantumimagesarecombinedtobuildthewholeprocessforquantumimagepro-cessingonFRQI.ThesimulationexperimentsonFRQIincludestoring,retrievingofimagesandadetectionofalineinbinaryimagesbyapplyingquantumFouriertransformasaprocessingoperation.ThecompressionratiosofQICbetweengroupsofsamecolorpositionsrangefrom68.75to90.63%onsingledigitimagesand6.67–31.62%ontheLenaimage.TheFRQIprovidesafoundationnotonlytoexpressimagesbutalsotoexploretheoreticalandpracticalaspectsofimageprocessingonquantumcomputers.KeywordsQuantumcomputation·Imagerepresentation·Imageprocessing·Imagecompression·QuantumFouriertransform1IntroductionIn1982,Feynmanproposedanovelcomputationmodel,namedquantumcomputers[6],basedonprinciplesofquantumphysicsthatseemedtobemorepowerfulthanclassicalones.AfterthatShor’spolynomialtimealgorithmfortheintegerfactoringP.Q.Le(B)·F.Dong·K.HirotaDepartmentofComputationalIntelligenceandSystemsScience,InterdisciplinaryGraduateSchoolofScienceandEngineering,TokyoInstituteofTechnology,G3-49,4259Nagatsuta,Midori-ku,Yokohama226-8502,Japane-mail:[e-mail];[e-mail][15]andGrover’sdatabasesearchalgorithm[8]wereessentialevidencessupportingthepowerofquantumcomputers.Quantumcomputationhasappearedinvariousareasofcomputersciencesuchasinformationtheory,cryptography,imageprocessing,etc.[14]becausethereareinefficienttasksonclassicalcomputersthatcanbeovercomedbyexploitingthepowerofthequantumcomputation.Processingandanalysisofimagesinparticularandvisualinformationingeneralonclassicalcom-putershavebeenstudiedextensively.Onquantumcomputers,theresearchonimageshasfacedfundamentaldifficultiesbecausethefieldisstillinitsinfancy.Tostartwith,whatarequantumimagesorhowdowerepresentimagesonquantumcomputers?Secondly,whatshouldwedotoprepareandprocessthequantumimagesonquantumcomputers?Researchinthefieldofquantumimageprocessingstartedwithproposalsonquan-tumimagerepresentationssuchasQubitLattice[17,18],RealKet[10]andquantumtransformsrelatedtoimageprocessingsuchasquantumFouriertransform[14],quan-tumdiscretecosinetransform[9,16],quantumWavelettransform[7].ThequantumimagesaretwodimensionalarraysofqubitsinRef.[17,18]andaquantumstateinRef.[10].ThequantumversionsofclassicalimageprocessingtransformssuchasFouriertransform,discretecosinetransform,etc.,aremoreefficientinquantumcom-putationthanclassicalones[14].Quantumalgorithmshavebeenappliedtoclassicalimageprocessingproblemsbecauseoftheirprovenefficiencyovertheclassicalver-sions[2,4,5].Inaddition,therearesomeclassicalimageprocessingoperationsthatcannotbeappliedonquantumimages,forexampleconvolutionandcorrelation[11],becausealloperationsinquantumcomputationmustbeinvertible.Thecomplexityofthepreparationofquantumimagesandtheapplicationofquantumtransformstoprocessquantumimages,however,havenotbeenstudied.Inthisresearch,aflexiblerepresentationofquantumimages(FRQI)whichcap-turesinformationaboutcolorsandtheircorrespondingpositionsinanimageintoanormalizedquantumstateisproposed.AftertheproposalofFRQI,thepaperstudiedthefollowingcomputationalandimageprocessingaspectsonFRQI:–Thecomplexity(thenumberofsimpleoperations)ofthepreparationforFRQI,–ThemethodtoreducenumberofsimpleoperationsthatareusedintheFRQIpreparationsteporquantumimagecompression(QIC),–ThreetypesofinvertibleimageprocessingoperatorsonFRQI.ThepreparationprocessforFRQIisindicatedbyusingHadamardandcontrolledrota-tionoperations.AsprovenbythePolynomialPreparationtheorem,thetotalnumberofsimpleoperationsusedintheprocessispolynomialforthenumberofqubitswhichareusedtoencodeallpositionsinanimage.Consideringcolorsindistinguishabletohumanvision,theQICalgorithmreducesthenumberofsimpleoperationsingroupsofthesamecolorpositionsbyintegratingcontrolledpartofthecontrolledrotationsinthegroups.ProcessingoperatorsonFRQIbasedonunitarytransformsaredividedintothreetypes;dealingwithonlycolors,colorsatsomepositionsandthecombinationofbothcolorsandpositions.ThesimulationexperimentsconfirmthecapacityofFRQIonstorageandretrievalquantumimages,compressionratioamongthesamecolorgroupsonQICalgorithmandanapplicationofanimageprocessingoperatorforthe123Aflexiblerepresentation65thirdtype,usingquantumFouriertransform,foralinedetectioninbinaryimagesonquantumcomputers.TheseresultsindicatethattheFRQIcanbethebasistorepresentandprocessquan-tumimages.ThepreparationandprocessingoperationsonFRQIimprovethewholeprocedureofquantumimageprocessing