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 size prec = QSearchCFNW (PrimSearch size prec)
data UQSearchEnv size = UQSearchEnv {
- search_arg_type :: VarType size
- pred_call_builder :: Arg size -> Arg size -> Arg size -> UStmt size
}
algoQSearchZalka :: forall ext size prec. (Integral size, RealFloat prec, TypingReqs size, size ~ SizeType ext, prec ~ PrecType ext) => FailProb prec -> Ident -> Ident -> UQSearchBuilder ext ()
groverK :: forall size. MetaParam size -> (Ident, VarType size) -> Ident -> (Ident -> Ident -> UStmt size) -> UStmt size
_EQSearch :: forall size prec. (Integral size, Floating prec) => size -> size -> FailProb prec -> prec
_EQSearchWorst :: forall size prec. (Integral size, Floating prec) => size -> FailProb prec -> prec
_QSearchZalka :: forall size prec. (Integral size, Floating prec) => size -> FailProb prec -> prec

Search Primitive

newtype QSearchCFNW size prec #

Constructors

QSearchCFNW (PrimSearch size prec)

Instances

Instances details

Generic (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Associated Types type Rep (QSearchCFNW size prec) :: Type -> Type # Methods from :: QSearchCFNW size prec -> Rep (QSearchCFNW size prec) x # to :: Rep (QSearchCFNW size prec) x -> QSearchCFNW size prec #
Read size => Read (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods readsPrec :: Int -> ReadS (QSearchCFNW size prec) # readList :: ReadS [QSearchCFNW size prec] # readPrec :: ReadPrec (QSearchCFNW size prec) # readListPrec :: ReadPrec [QSearchCFNW size prec] #
Show size => Show (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods showsPrec :: Int -> QSearchCFNW size prec -> ShowS # show :: QSearchCFNW size prec -> String # showList :: [QSearchCFNW size prec] -> ShowS #
Eq size => Eq (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods (==) :: QSearchCFNW size prec -> QSearchCFNW size prec -> Bool # (/=) :: QSearchCFNW size prec -> QSearchCFNW size prec -> Bool #
Show size => SerializePrim (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods primNames :: [Ident] # primNameOf :: QSearchCFNW size prec -> Ident # parsePrimParams :: TokenParser () -> Ident -> Parser (QSearchCFNW size prec) # printPrimParams :: QSearchCFNW size prec -> [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] #
(RealFloat prec, Show prec) => QuantumCompilePrim (QSearchCFNW SizeT prec) SizeT prec #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods compileQPrim :: forall ext' m (shape :: Type -> Type). (m ~ PrimCompileMonad ext' (QSearchCFNW SizeT prec), SizeT ~ SizeType ext', prec ~ PrecType ext', shape ~ PrimFnShape (QSearchCFNW SizeT prec)) => QSearchCFNW SizeT prec -> FailProb prec -> m (ProcDef SizeT) #
(TypingReqs size, Integral size, RealFloat prec, Show prec) => UnitaryCompilePrim (QSearchCFNW size prec) size prec #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods compileUPrim :: forall ext' m (shape :: Type -> Type). (m ~ PrimCompileMonad ext' (QSearchCFNW size prec), size ~ SizeType ext', prec ~ PrecType ext', shape ~ PrimFnShape (QSearchCFNW size prec)) => QSearchCFNW size prec -> FailProb prec -> m (ProcDef 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] #
(size ~ SizeT, Floating prec, RVType prec prec) => QuantumExpCostPrim (QSearchCFNW size prec) size prec #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods quantumExpQueryCostsQuantum :: (shape ~ PrimFnShape (QSearchCFNW size prec), m ~ EvaluationMonad prec) => QSearchCFNW size prec -> FailProb prec -> shape ([Value size] -> m [Value size]) -> shape [([Value size], prec)] # quantumExpQueryCostsUnitary :: (shape ~ PrimFnShape (QSearchCFNW size prec), m ~ EvaluationMonad prec) => QSearchCFNW size prec -> FailProb prec -> shape ([Value size] -> m [Value size]) -> shape (UnitaryQueries prec) # quantumExpExprCosts :: forall shape cost m. (CostModel cost, prec ~ PrecType cost, shape ~ PrimFnShape (QSearchCFNW size prec), m ~ EvaluationMonad prec) => QSearchCFNW size prec -> FailProb prec -> shape ([Value size] -> m [Value size]) -> cost #
(TypingReqs size, Integral size, SizeToPrec size prec, Floating prec) => QuantumHavocCostPrim (QSearchCFNW size prec) size prec #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods quantumQueryCostsQuantum :: QSearchCFNW size prec -> FailProb prec -> PrimFnShape (QSearchCFNW size prec) prec # quantumQueryCostsUnitary :: QSearchCFNW size prec -> FailProb prec -> PrimFnShape (QSearchCFNW size prec) (UnitaryQueries prec) # quantumExprCosts :: (CostModel cost, prec ~ PrecType cost) => QSearchCFNW size prec -> FailProb prec -> cost #
(TypingReqs size, Integral size, Floating prec) => UnitaryCostPrim (QSearchCFNW size prec) size prec #	Compute the unitary cost using the QSearch_Zalka cost formula.
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods unitaryQueryCosts :: QSearchCFNW size prec -> FailProb prec -> PrimFnShape (QSearchCFNW size prec) (UnitaryQueries prec) # unitaryExprCosts :: (CostModel cost, prec ~ PrecType cost) => QSearchCFNW size prec -> FailProb prec -> cost #
(PrimSearch size prec) :<: (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW Methods inject :: PrimSearch size prec -> QSearchCFNW size prec # project :: QSearchCFNW size prec -> Maybe (PrimSearch size prec) #
type Rep (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type Rep (QSearchCFNW size prec) = 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 size prec))))
type PrecType (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type PrecType (QSearchCFNW size prec) = prec
type SizeType (QSearchCFNW size prec) #
Instance details Defined in Traq.Primitives.Search.QSearchCFNW type SizeType (QSearchCFNW size prec) = size
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 size #

Information for building QSearch_Zalka

Constructors

UQSearchEnv
Fields search_arg_type :: VarType size pred_call_builder :: Arg size -> Arg size -> Arg size -> UStmt size

algoQSearchZalka #

Arguments

:: forall ext size prec. (Integral size, RealFloat prec, TypingReqs size, size ~ SizeType ext, prec ~ PrecType ext)
=> FailProb prec	max. error (TV/trace-norm)
-> Ident	output bit
-> Ident	output value of search
-> UQSearchBuilder ext ()

CQ Implementation

groverK #

Arguments

:: forall size. MetaParam size	number of rounds
-> (Ident, VarType size)	the element and type to search for. `x : T`
-> Ident	the output bit
-> (Ident -> Ident -> UStmt size)	run the predicate
-> UStmt size

Run K grover iterations

Cost Formulas

_EQSearch :: forall size prec. (Integral size, Floating prec) => size -> size -> FailProb prec -> prec #

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

_EQSearchWorst :: forall size prec. (Integral size, Floating prec) => size -> FailProb prec -> prec #

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

_QSearchZalka :: forall size prec. (Integral size, Floating prec) => size -> FailProb prec -> prec #