v      مسائل بهينه سازي

v       محاسبات كوانتومي

v       كاربرد محاسبات كوانتومي در حل مسائل بهينه سازي

در علوم رياضي و كامپيوتر ، مساله بهينه سازي ، مساله يافتن بهترين راه حل از ميان تمامي راه حلهاي ممكن مي باشد. در حقيقت يك مساله بهينه سازي مانند A يك چهار تايي بصورت  (I,f,m,g) مي باشد كه در آن :

Ø       I مجموعه اي از نمونه ها.

Ø       اگر x نمونه اي در I باشد، f(x) مجموعه راه حلهاي ممكن براي x است.

Ø       اگر x يك نمونه و y يك راه حل ممكن براي x باشد، m(x,y) كه معمولا عددي مثبت است،  معيار سنجش y مي باشد.

Ø       g تابع هدف مي باشد كه min يا max مي باشد.

هدف يافتن يك راه حل بهينه مانند y براي برخي نمونه ها مي باشد بطوريكه:

كلاس P شامل آن دسته از مسائلي است كه در يك زمان چند جمله اي قابل حل هستند.( مسائلي كه مي توانند در زمان O(n^k) حل شوند كه در آن k يك عددثابت و n اندازه ورودي مساله مي باشد.)

كلاس NP شامل آن دسته از مسائلي است كه در يك زمان چند جمله اي، تصديق پذير(verifiable) هستند.( ممكن است خود مساله در يك زمان چند جمله اي قابل حل نباشد، اما اگر يك راه حل براي آن ارائه شود، مي توان در يك زمان چندجمله اي صحت آن راه حل را مشخص نمود.)

عمده مسائل بهينه سازي، در كلاس NP قرار مي گيرند چرا كه حل مساله در يك زمان چند جمله اي قابل انجام نمي باشد، ولي مي توان صحت يك راه حل ارائه شده را در يك زمان چندجمله اي بررسي نمود.