Safe Haskell	Safe-Inferred
Language	Haskell2010

Traq.Primitives.Search.QSearchCFNW

Contents

Search Primitive
Unitary Implementation
CQ Implementation
Cost Formulas

Description

Cost formulas and implementations of the quantum search algorithms in Ref [1].

References:

Quantifying Grover speed-ups beyond asymptotic analysis

Synopsis

newtype QSearchCFNW sizeT precT = QSearchCFNW (PrimSearch sizeT precT)
data UQSearchEnv sizeT = UQSearchEnv {
- search_arg_type :: VarType sizeT
- pred_call_builder :: Ident -> Ident -> Ident -> UStmt sizeT
}
algoQSearchZalka :: forall ext sizeT precT. (Integral sizeT, RealFloat precT, TypingReqs sizeT, sizeT ~ SizeType ext, precT ~ PrecType ext) => FailProb precT -> Ident -> UQSearchBuilder ext ()
_EQSearch :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> sizeT -> FailProb precT -> precT
_EQSearchWorst :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> FailProb precT -> precT
_QSearchZalka :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> FailProb precT -> precT

Search Primitive

newtype QSearchCFNW sizeT precT #

Constructors

QSearchCFNW (PrimSearch sizeT precT)

Instances

Instances details

(Integral sizeT, RealFloat precT, sizeT ~ SizeT, Show sizeT, Show precT, TypingReqs sizeT) => CompileQ (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods compileQ :: forall ext' m. (m ~ CompilerT ext', SizeType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) ~ SizeType ext', PrecType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) ~ PrecType ext', CompileQ ext') => AnnFailProb (Primitive (QSearchCFNW sizeT precT)) -> [Ident] -> m (Stmt (SizeType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))))) #
(Integral sizeT, RealFloat precT, Show sizeT, Show precT, TypingReqs sizeT, SizeToPrec sizeT precT) => CompileU (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods compileU :: forall ext' m. (m ~ CompilerT ext', SizeType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) ~ SizeType ext', PrecType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))) ~ PrecType ext') => AnnFailProb (Primitive (QSearchCFNW sizeT precT)) -> [Ident] -> m (UStmt (SizeType (AnnFailProb (Primitive (QSearchCFNW sizeT precT))))) #
Generic (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Associated Types type Rep (QSearchCFNW sizeT precT) :: Type -> Type # Methods from :: QSearchCFNW sizeT precT -> Rep (QSearchCFNW sizeT precT) x # to :: Rep (QSearchCFNW sizeT precT) x -> QSearchCFNW sizeT precT #
Read sizeT => Read (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods readsPrec :: Int -> ReadS (QSearchCFNW sizeT precT) # readList :: ReadS [QSearchCFNW sizeT precT] # readPrec :: ReadPrec (QSearchCFNW sizeT precT) # readListPrec :: ReadPrec [QSearchCFNW sizeT precT] #
Show sizeT => Show (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods showsPrec :: Int -> QSearchCFNW sizeT precT -> ShowS # show :: QSearchCFNW sizeT precT -> String # showList :: [QSearchCFNW sizeT precT] -> ShowS #
Eq sizeT => Eq (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods (==) :: QSearchCFNW sizeT precT -> QSearchCFNW sizeT precT -> Bool # (/=) :: QSearchCFNW sizeT precT -> QSearchCFNW sizeT precT -> Bool #
Show sizeT => SerializePrim (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods primNames :: [Ident] # primNameOf :: QSearchCFNW sizeT precT -> Ident # parsePrimParams :: TokenParser () -> Ident -> Parser (QSearchCFNW sizeT precT) # printPrimParams :: QSearchCFNW sizeT precT -> [String] #
MapSize (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Associated Types type MappedSize (QSearchCFNW size prec) size' # Methods mapSize :: (size0 ~ SizeType (QSearchCFNW size prec), size' ~ SizeType ext', ext' ~ MappedSize (QSearchCFNW size prec) size') => (size0 -> size') -> QSearchCFNW size prec -> ext' #
TypingReqs size => TypeCheckPrim (QSearchCFNW size prec) size #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods inferRetTypesPrim :: forall ext' shape m. (m ~ TypeChecker ext', size ~ SizeType ext', shape ~ PrimFnShape (QSearchCFNW size prec)) => QSearchCFNW size prec -> shape (FnType size) -> m [VarType size] #
EvalPrim (QSearchCFNW size prec) size prec #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods evalPrim :: forall ext' shape m. (Evaluatable ext' size prec, m ~ Evaluator ext', SizeType ext' ~ size, PrecType ext' ~ prec, shape ~ PrimFnShape (QSearchCFNW size prec)) => QSearchCFNW size prec -> shape ([Value size] -> m [Value size]) -> m [Value size] #
(sizeT ~ SizeT, Floating precT, RVType precT precT) => QuantumExpCostPrim (QSearchCFNW sizeT precT) sizeT precT #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods quantumExpQueryCostsQuantum :: (shape ~ PrimFnShape (QSearchCFNW sizeT precT), m ~ EvaluationMonad precT) => QSearchCFNW sizeT precT -> FailProb precT -> shape ([Value sizeT] -> m [Value sizeT]) -> shape [([Value sizeT], precT)] # quantumExpQueryCostsUnitary :: (shape ~ PrimFnShape (QSearchCFNW sizeT precT), m ~ EvaluationMonad precT) => QSearchCFNW sizeT precT -> FailProb precT -> shape ([Value sizeT] -> m [Value sizeT]) -> shape (UnitaryQueries precT) # quantumExpExprCosts :: forall shape cost m. (CostModel cost, precT ~ PrecType cost, shape ~ PrimFnShape (QSearchCFNW sizeT precT), m ~ EvaluationMonad precT) => QSearchCFNW sizeT precT -> FailProb precT -> shape ([Value sizeT] -> m [Value sizeT]) -> cost #
(TypingReqs sizeT, Integral sizeT, SizeToPrec sizeT precT, Floating precT) => QuantumHavocCostPrim (QSearchCFNW sizeT precT) sizeT precT #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods quantumQueryCostsQuantum :: QSearchCFNW sizeT precT -> FailProb precT -> PrimFnShape (QSearchCFNW sizeT precT) precT # quantumQueryCostsUnitary :: QSearchCFNW sizeT precT -> FailProb precT -> PrimFnShape (QSearchCFNW sizeT precT) (UnitaryQueries precT) # quantumExprCosts :: (CostModel cost, precT ~ PrecType cost) => QSearchCFNW sizeT precT -> FailProb precT -> cost #
(TypingReqs sizeT, Integral sizeT, Floating precT) => UnitaryCostPrim (QSearchCFNW sizeT precT) sizeT precT #	Compute the unitary cost using the QSearch_Zalka cost formula.
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods unitaryQueryCosts :: QSearchCFNW sizeT precT -> FailProb precT -> PrimFnShape (QSearchCFNW sizeT precT) (UnitaryQueries precT) # unitaryExprCosts :: (CostModel cost, precT ~ PrecType cost) => QSearchCFNW sizeT precT -> FailProb precT -> cost #
(PrimSearch sizeT precT) :<: (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods inject :: PrimSearch sizeT precT -> QSearchCFNW sizeT precT # project :: QSearchCFNW sizeT precT -> Maybe (PrimSearch sizeT precT) #
type Rep (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type Rep (QSearchCFNW sizeT precT) = D1 ('MetaData "QSearchCFNW" "Traq.Primitives.Search.QSearchCFNW" "traq-0.2.0.0-inplace" 'True) (C1 ('MetaCons "QSearchCFNW" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (PrimSearch sizeT precT))))
type PrecType (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type PrecType (QSearchCFNW sizeT precT) = precT
type SizeType (QSearchCFNW sizeT precT) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type SizeType (QSearchCFNW sizeT precT) = sizeT
type PrimFnShape (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type PrimFnShape (QSearchCFNW size prec) = BooleanPredicate
type MappedSize (QSearchCFNW size prec) size' #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type MappedSize (QSearchCFNW size prec) size' = QSearchCFNW size' prec

Unitary Implementation

data UQSearchEnv sizeT #

Information for building QSearch_Zalka

Constructors

UQSearchEnv
Fields search_arg_type :: VarType sizeT pred_call_builder :: Ident -> Ident -> Ident -> UStmt sizeT

algoQSearchZalka #

Arguments

:: forall ext sizeT precT. (Integral sizeT, RealFloat precT, TypingReqs sizeT, sizeT ~ SizeType ext, precT ~ PrecType ext)
=> FailProb precT	max. error (TV/trace-norm)
-> Ident	output bit
-> UQSearchBuilder ext ()

CQ Implementation

Cost Formulas

_EQSearch :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> sizeT -> FailProb precT -> precT #

https://arxiv.org/pdf/2203.04975v2, Eq. 2

_EQSearchWorst :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> FailProb precT -> precT #

https://arxiv.org/pdf/2203.04975v2, Eq. 4

_QSearchZalka :: forall sizeT precT. (Integral sizeT, Floating precT) => sizeT -> FailProb precT -> precT #