সহজ ইনপুটগুলিতে উন্নত কোয়ান্টাম কোয়েরি জটিলতা

সহজ ইনপুটগুলিতে উন্নত কোয়ান্টাম কোয়েরি জটিলতা

নোয়েল টি. অ্যান্ডারসন1, জে-ইউ চুং1, শেলবি কিমেল1, দা-ইওন কোহ2, এবং জিয়াওহান ইয়ে1,3

1মিডলবেরি কলেজ, মিডলবেরি, ভিটি, মার্কিন যুক্তরাষ্ট্র
2উইলিয়ামস কলেজ, উইলিয়ামসটাউন, এমএ, মার্কিন যুক্তরাষ্ট্র
3ব্রাউন ইউনিভার্সিটি, প্রভিডেন্স, আরআই, মার্কিন যুক্তরাষ্ট্র

এই কাগজ আকর্ষণীয় খুঁজুন বা আলোচনা করতে চান? স্কাইটে বা স্কাইরেটে একটি মন্তব্য দিন.

বিমূর্ত

ফাংশন মূল্যায়নের জন্য কোয়ান্টাম স্প্যান প্রোগ্রাম অ্যালগরিদম কখনও কখনও ক্যোয়ারী জটিলতা কমিয়ে দেয় যখন প্রতিশ্রুতি দেওয়া হয় যে ইনপুটটির একটি নির্দিষ্ট কাঠামো রয়েছে। আমরা একটি পরিবর্তিত স্প্যান প্রোগ্রাম অ্যালগরিদম ডিজাইন করি যাতে দেখা যায় যে এই উন্নতিগুলি সময়ের আগে কোনও প্রতিশ্রুতি ছাড়াই টিকে থাকে এবং আমরা এই পদ্ধতিটিকে রাষ্ট্রীয় রূপান্তরের আরও সাধারণ সমস্যার দিকে প্রসারিত করি। একটি অ্যাপ্লিকেশান হিসাবে, আমরা বেশ কিছু অনুসন্ধান সমস্যার জন্য গড় ক্যোয়ারী জটিলতায় সূচকীয় এবং সুপারপলিনোমিয়াল কোয়ান্টাম সুবিধাগুলি প্রমাণ করি, পরামর্শ দিয়ে মন্টানারোর অনুসন্ধানকে সাধারণীকরণ করে [মন্টানারো, টিকিউসি 2010]।

আমরা আশা করি যে ক্লাসিক্যাল অ্যালগরিদমের মতো কোয়ান্টাম অ্যালগরিদমগুলি সহজ ইনপুটগুলিতে দ্রুত চালানো উচিত। উদাহরণ স্বরূপ, যদি আপনি একটি ক্রমবিহীন তালিকায় একটি আইটেম অনুসন্ধান করেন এবং সেই আইটেমের অনেক কপি থাকে, তাহলে আমরা আশা করব এই পরিস্থিতিতে কোয়ান্টাম অ্যালগরিদম দ্রুত চলবে যখন শুধুমাত্র একটি চিহ্নিত আইটেম থাকে, এমনকি না জেনেও। সময়ের আগে লক্ষ্য আইটেম সংখ্যা. প্রকৃতপক্ষে, অনুসন্ধানের সমস্যার জন্য, সহজ ইনপুটগুলিতে এই ধরনের সুবিধা কীভাবে পাওয়া যায় তা জানা যায়। যাইহোক, অনুসন্ধানের বাইরে সমস্যাগুলির জন্য এই ধারণাটিকে সাধারণীকরণ করা চ্যালেঞ্জিং যখন গণনাটি যথেষ্ট দীর্ঘ সময় ধরে চলার সময় পতাকাঙ্কিত করার কোনও সুস্পষ্ট উপায় নেই। আমরা ক্যোয়ারী মডেলে বেশ কিছু জনপ্রিয় অ্যালগরিদমিক ফ্রেমওয়ার্ক পরিবর্তন করে ফ্ল্যাগ তৈরি করি যা আমাদেরকে সতর্ক করে যে গণনাটি যথেষ্ট দীর্ঘ সময় ধরে চলছে কিনা, আমাদের সহজ ইনপুটগুলিতে অ্যালগরিদমটি তাড়াতাড়ি শেষ করার অনুমতি দেয়, দৃষ্টান্তটি সহজ বা কঠিন কিনা তা আগে থেকে না জেনে। একটি অ্যাপ্লিকেশন হিসাবে, একটি সমস্যার জন্য সহজ এবং কঠিন উভয় ইনপুটগুলির একটি বিতরণ দেওয়া হলে, আমরা গড় ক্যোয়ারী জটিলতা বিশ্লেষণ করতে পারি। আমরা দেখাই যে অনুসন্ধানের সমস্যাগুলির জন্য ইনপুটগুলির নির্দিষ্ট বিতরণগুলি ক্লাসিক্যাল অ্যালগরিদমের তুলনায় বড় গড় কোয়ান্টাম কোয়েরি সুবিধা দেয়।

► বিবিটেক্স ডেটা

। তথ্যসূত্র

[1] আন্দ্রিস অ্যাম্বাইনিস এবং রোনাল্ড ডি উলফ। গড়-কেস কোয়ান্টাম কোয়েরি জটিলতা। পদার্থবিজ্ঞানের জার্নাল A: গাণিতিক এবং সাধারণ, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302।
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] ডরিট আহারোনভ। কোয়ান্টাম কম্পিউটেশন। কম্পিউটেশনাল ফিজিক্স VI এর বার্ষিক পর্যালোচনা, পৃষ্ঠা 259–346, 1999. doi:10.1142/​9789812815569_0007।
https://​doi.org/​10.1142/​9789812815569_0007

[3] মিশেল বোয়ার, গিলস ব্রাসার্ড, পিটার হায়ার এবং অ্যালাইন ট্যাপ। কোয়ান্টাম অনুসন্ধানে টাইট বাউন্ডস। Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -পি.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[4] আলেকজান্ডার বেলভস। ধ্রুব-আকারের 1-শংসাপত্র সহ ফাংশনের জন্য স্প্যান প্রোগ্রাম: বর্ধিত বিমূর্ত। থিওরি অফ কম্পিউটিং, STOC '12, পৃষ্ঠা 77–84, 2012. doi:10.1145/​2213977.2213985-এর উপর চল্লিশ-চতুর্থ বার্ষিক ACM সিম্পোজিয়ামের কার্যপ্রণালীতে।
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca, এবং Alain Tapp. কোয়ান্টাম প্রশস্ততা পরিবর্ধন এবং অনুমান। কোয়ান্টাম গণনা এবং তথ্যে, কনটেম্পের ভলিউম 305। গণিত।, পৃষ্ঠা 53-74। আমের। গণিত Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215।
https://​doi.org/​10.1090/​conm/​305/​05215

[6] Gilles Brassard, Peter Høyer এবং Alain Tapp। কোয়ান্টাম গণনা। অটোমেটা, ভাষা এবং প্রোগ্রামিং-এ, পৃষ্ঠা 820-831, 1998. doi:10.1007/​BFb0055105।
https://​doi.org/​10.1007/​BFb0055105

[7] আলেকজান্ডার বেলভস এবং বেন ডব্লিউ রিচার্ড। st-সংযোগ এবং নখর সনাক্তকরণের জন্য স্প্যান প্রোগ্রাম এবং কোয়ান্টাম অ্যালগরিদম। লেকচার নোটস ইন কম্পিউটার সায়েন্স, 7501 LNCS:193–204, 2012. doi:10.1007/​978-3-642-33090-2_18।
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] আলেকজান্ডার বেলভস এবং আনসিস রোসমানিস। কোয়ান্টাম স্টেটের সাথে আনুমানিক গণনার জন্য টাইট কোয়ান্টাম লোয়ার বাউন্ড। 2020। arXiv:2002.06879।
arXiv: 2002.06879

[9] সালমান বেগি এবং লীলা তাগাভি। ক্লাসিক্যাল সিদ্ধান্ত গাছের উপর ভিত্তি করে কোয়ান্টাম গতি। কোয়ান্টাম, 4:241, 2020। doi:10.22331/q-2020-03-02-241।
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] আলেকজান্ডার বেলভস এবং ডুয়াল ইয়ল্কু। লাস ভেগাস এবং কোয়ান্টাম প্রতিপক্ষের একমুখী টিকিট। 2023. arXiv:2301.02003।
arXiv: 2301.02003

[11] রিচার্ড। ক্লিভ, আর্টার। Ekert, Chiara Macchiavello এবং Michele Mosca। কোয়ান্টাম অ্যালগরিদম পুনর্বিবেচনা করা হয়েছে। লন্ডনের রয়্যাল সোসাইটির কার্যধারা। সিরিজ A: গাণিতিক, শারীরিক এবং প্রকৌশল বিজ্ঞান, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / RSSpa.1998.0164

[12] আরজান কর্নেলিসেন, স্টেসি জেফরি, মারিস ওজোলস এবং আলভারো পিড্রাফিটা। স্প্যান প্রোগ্রাম এবং কোয়ান্টাম সময় জটিলতা। কম্পিউটার সায়েন্সের গাণিতিক ভিত্তির উপর 45তম আন্তর্জাতিক সিম্পোজিয়ামে (MFCS 2020)। Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https://​/​doi.org/​10.4230/​LIPIcs.MFCS.2020.26

[13] ক্রিস ক্যাড, অ্যাশলে মন্টানারো এবং আলেকজান্ডার বেলভস। চক্র সনাক্তকরণ এবং দ্বিপক্ষীয়তা পরীক্ষা করার জন্য সময় এবং স্থান দক্ষ কোয়ান্টাম অ্যালগরিদম। কোয়ান্টাম তথ্য ও গণনা, 18(1-2):18–50, 2018।

[14] কাই ডিলোরেঞ্জো, শেলবি কিমেল এবং আর. টিল উইটার। স্ট-কানেক্টিভিটির জন্য কোয়ান্টাম অ্যালগরিদমের অ্যাপ্লিকেশন। কোয়ান্টাম কম্পিউটেশন, কমিউনিকেশন অ্যান্ড ক্রিপ্টোগ্রাফি (TQC 14) তত্ত্বের 2019তম সম্মেলনে, পৃষ্ঠা 6:1–6:14, 2019. doi:10.4230/​LIPIcs.TQC.2019.6।
https://​/​doi.org/​10.4230/​LIPIcs.TQC.2019.6

[15] দিমিত্রি গ্রিনকো, জুলিয়েন গ্যাকন, ক্রিস্টা জাউফাল এবং স্টেফান ওয়ার্নার। পুনরাবৃত্তিমূলক কোয়ান্টাম প্রশস্ততা অনুমান। npj কোয়ান্টাম তথ্য, 7(1):52, মার্চ 2021। doi:10.1038/​s41534-021-00379-1।
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] লাভ কে গ্রোভার। কোয়ান্টাম মেকানিক্স একটি খড়ের গাদায় একটি সুই অনুসন্ধান করতে সাহায্য করে। শারীরিক পর্যালোচনা পত্র, 79(2):325–328, 1997. doi:10.1103/​physRevLett.79.325.
https: / / doi.org/ 10.1103 / ফিজিরভাইলেট .79.325

[17] ওয়াসিলি হোফডিং। আবদ্ধ র্যান্ডম ভেরিয়েবলের সমষ্টির জন্য সম্ভাব্যতা অসমতা। আমেরিকান স্ট্যাটিস্টিক্যাল অ্যাসোসিয়েশনের জার্নাল, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830।
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] সুয়োশি ইতো এবং স্টেসি জেফরি। আনুমানিক স্প্যান প্রোগ্রাম। অ্যালগরিদমিকা, 81(6):2158–2195, 2019। doi:10.1007/​s00453-018-0527-1।
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] মাইকেল জ্যারেট, স্টেসি জেফরি, শেলবি কিমেল এবং আলভারো পিড্রাফিটা। সংযোগ এবং সম্পর্কিত সমস্যার জন্য কোয়ান্টাম অ্যালগরিদম। 26তম বার্ষিক ইউরোপীয় সিম্পোজিয়াম অন অ্যালগরিদম (ESA 2018), পৃষ্ঠা 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49।
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] আলেক্সি ওয়াই কিতায়েভ। কোয়ান্টাম পরিমাপ এবং অ্যাবেলিয়ান স্ট্যাবিলাইজার সমস্যা। 1995. arXiv:quant-ph/​9511026.
আরএক্সিভ: কোয়ান্ট-পিএইচ / 9511026

[21] ট্রয় লি, রজত মিত্তাল, বেন ডব্লিউ রিচার্ড, রবার্ট স্পালেক এবং মারিও সেজেডি। রাজ্য রূপান্তরের কোয়ান্টাম কোয়েরি জটিলতা। 2011 সালে IEEE 52 তম বার্ষিক সিম্পোজিয়াম অন কম্পিউটার সায়েন্স ফাউন্ডেশন, পৃষ্ঠা 344–353, 2011. doi:10.1109/FOCS.2011.75।
https://​doi.org/​10.1109/FOCS.2011.75

[22] ফ্রেডেরিক ম্যাগনিজ, অশ্বিন নায়ক, জেরেমি রোল্যান্ড এবং মিক্লোস সানথা। কোয়ান্টাম ওয়াকের মাধ্যমে অনুসন্ধান করুন। সিয়াম জার্নাল অন কম্পিউটিং, 40(1):142–164, 2011। doi:10.1137/​090745854।
https: / / doi.org/ 10.1137 / 090745854

[23] অ্যাশলে মন্টানারো। পরামর্শ দিয়ে কোয়ান্টাম অনুসন্ধান করুন। কনফারেন্স অন কোয়ান্টাম কম্পিউটেশন, কমিউনিকেশন এবং ক্রিপ্টোগ্রাফি, পৃষ্ঠা 77-93। স্প্রিংগার, 2010. doi:10.1007/​978-3-642-18073-6_7।
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] বেন ডব্লিউ রিচার্ড। স্প্যান প্রোগ্রাম এবং কোয়ান্টাম কোয়েরি জটিলতা: প্রতিটি বুলিয়ান ফাংশনের জন্য সাধারণ প্রতিপক্ষের আবদ্ধতা প্রায় শক্ত। 50 তম বার্ষিক IEEE সিম্পোজিয়াম অন কম্পিউটার সায়েন্স ফাউন্ডেশন, পৃষ্ঠা 544–551, 2009. doi:10.1109/FOCS.2009.55.
https://​doi.org/​10.1109/FOCS.2009.55

[25] বেন ডব্লিউ রিচার্ড। কোয়ান্টাম কোয়েরি অ্যালগরিদমের প্রতিফলন। ডিসক্রিট অ্যালগরিদম, প্রসিডিংস, পৃষ্ঠা 2011-560 সংক্রান্ত 569 বার্ষিক ACM-SIAM সিম্পোজিয়ামের কার্যধারায়। 2011. doi:10.1137/​1.9781611973082.44।
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] লীলা তাগাভী। ওরাকল সনাক্তকরণ সমস্যার জন্য সরলীকৃত কোয়ান্টাম অ্যালগরিদম। কোয়ান্টাম মেশিন ইন্টেলিজেন্স, 4(2):19, 2022। doi:10.1007/​s42484-022-00080-2।
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

দ্বারা উদ্ধৃত

[১] স্টেসি জেফরি, শেলবি কিমেল এবং আলভারো পিড্রাফিটা, "পাথ-এজ স্যাম্পলিং এর জন্য কোয়ান্টাম অ্যালগরিদম", arXiv: 2303.03319, (2023).

[২] মাইকেল চেকানস্কি, শেলবি কিমেল, এবং আর. টিল উইটার, "শক্তিশালী এবং মহাকাশ-দক্ষ দ্বৈত প্রতিপক্ষ কোয়ান্টাম কোয়েরি অ্যালগরিদম", arXiv: 2306.15040, (2023).

উপরের উদ্ধৃতিগুলি থেকে প্রাপ্ত এসএও / নাসার এডিএস (সর্বশেষে সফলভাবে 2024-04-11 15:45:18 আপডেট হয়েছে)। সমস্ত প্রকাশক উপযুক্ত এবং সম্পূর্ণ উদ্ধৃতি ডেটা সরবরাহ না করায় তালিকাটি অসম্পূর্ণ হতে পারে।

On ক্রসরেফ এর উদ্ধৃত পরিষেবা উদ্ধৃতি রচনার কোনও ডেটা পাওয়া যায় নি (শেষ চেষ্টা 2024-04-11 15:45:17)।

সময় স্ট্যাম্প:

থেকে আরো কোয়ান্টাম জার্নাল