آسان ان پٹس پر بہتر کوانٹم سوال کی پیچیدگی

آسان ان پٹس پر بہتر کوانٹم سوال کی پیچیدگی

ٹائم سٹیمپ: 8 اپریل 2024 صبح 11:29 بجے

نول ٹی اینڈرسن1، جے یو چنگ1, شیلبی کامل1، دا یون کوہ2، اور Xiaohan Ye1,3

1Middlebury College, Middlebury, VT, USA
2ولیمز کالج، ولیم ٹاؤن، ایم اے، امریکہ
3براؤن یونیورسٹی، پروویڈنس، RI، USA

اس کاغذ کو دلچسپ لگتا ہے یا اس پر بات کرنا چاہتے ہیں؟ SciRate پر تبصرہ کریں یا چھوڑیں۔.

خلاصہ

فنکشن کی تشخیص کے لیے کوانٹم اسپین پروگرام الگورتھم نے بعض اوقات استفسار کی پیچیدگی کو کم کر دیا ہے جب یہ وعدہ کیا جاتا ہے کہ ان پٹ کا ایک خاص ڈھانچہ ہے۔ ہم ایک ترمیم شدہ اسپین پروگرام الگورتھم کو یہ دکھانے کے لیے ڈیزائن کرتے ہیں کہ یہ بہتری وقت سے پہلے کسی وعدے کے بغیر بھی برقرار رہتی ہے، اور ہم اس نقطہ نظر کو ریاست کی تبدیلی کے زیادہ عمومی مسئلے تک بڑھاتے ہیں۔ ایک ایپلیکیشن کے طور پر، ہم متعدد تلاش کے مسائل کے لیے اوسط استفسار کی پیچیدگی میں ایکسپونینشل اور سپر پولینومیئل کوانٹم فوائد ثابت کرتے ہیں، مونٹانارو کی تلاش کو مشورے کے ساتھ عام کرتے ہوئے [مونٹینارو، ٹی کیو سی 2010]۔

آسان ان پٹس پر بہتر کوانٹم استفسار کی پیچیدگی PlatoBlockchain ڈیٹا انٹیلی جنس۔ عمودی تلاش۔ عی

نمایاں تصویر: فیصلہ ٹری ہمارے الگورتھم میں سے ایک بنانے کے لیے استعمال ہوتا ہے۔

مقبول خلاصہ

ہم توقع کرتے ہیں کہ کوانٹم الگورتھم، کلاسیکی الگورتھم کی طرح، آسان ان پٹ پر تیزی سے چلنا چاہیے۔ مثال کے طور پر، اگر آپ غیر ترتیب شدہ فہرست میں کسی آئٹم کو تلاش کر رہے ہیں، اور اس آئٹم کی بہت سی کاپیاں موجود ہیں، تو ہم توقع کریں گے کہ کوانٹم الگورتھم اس صورت حال کے مقابلے میں زیادہ تیزی سے چلنا چاہیے جب کہ اگر صرف ایک نشان زد آئٹم ہے، چاہے وہ جانے بغیر۔ وقت سے پہلے ہدف اشیاء کی تعداد۔ درحقیقت، تلاش کے مسئلے کے لیے، یہ معلوم ہے کہ آسان ان پٹ پر اس طرح کا فائدہ کیسے حاصل کیا جائے۔ تاہم، اس خیال کو تلاش سے باہر کے مسائل کے لیے عام کرنا ایک مشکل کام ہے جب کمپیوٹیشن کافی عرصے تک جاری رہنے پر پرچم لگانے کا کوئی واضح طریقہ نہیں ہے۔ ہم استفسار کے ماڈل میں کئی مشہور الگورتھمک فریم ورکس میں ترمیم کرتے ہیں تاکہ ایسے جھنڈے تیار کیے جا سکیں جو ہمیں متنبہ کرتے ہیں کہ آیا کمپیوٹیشن کافی دیر تک چلی ہے، ہمیں آسان ان پٹس پر الگورتھم کو جلد ختم کرنے کی اجازت دیتا ہے، یہ جانے بغیر کہ مثال آسان ہے یا مشکل۔ ایک ایپلیکیشن کے طور پر، کسی مسئلے کے لیے آسان اور مشکل دونوں طرح کے ان پٹ کی تقسیم کے پیش نظر، ہم اوسط سوال کی پیچیدگی کا تجزیہ کر سکتے ہیں۔ ہم یہ ظاہر کرتے ہیں کہ تلاش کے مسائل کے لیے آدانوں کی کچھ تقسیم کلاسیکی الگورتھم پر اوسط کوانٹم استفسار کے بڑے فوائد حاصل کرتی ہے۔

► BibTeX ڈیٹا

► حوالہ جات

ہے [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-سرٹیفکیٹس کے ساتھ فنکشنز کے لیے اسپین پروگرام: توسیعی خلاصہ۔ تھیوری آف کمپیوٹنگ پر 12ویں سالانہ ACM سمپوزیم کی کارروائی میں، STOC '77، صفحہ 84–2012، 10.1145. doi:2213977.2213985/​XNUMX۔
https://​doi.org/​10.1145/​2213977.2213985

ہے [5] Gilles Brassard، Peter Høyer، Michele Mosca، اور Alain Tapp۔ کوانٹم طول و عرض پروردن اور تخمینہ۔ کوانٹم کمپیوٹیشن اور معلومات میں، Contemp کا حجم 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-connectivity اور پنجوں کا پتہ لگانے کے لیے اسپین پروگرامز اور کوانٹم الگورتھم۔ کمپیوٹر سائنس میں لیکچر نوٹس، 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.
آر ایکس سی: 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.
آر ایکس سی: 2301.02003

ہے [11] رچرڈ۔ Cleve، Artur. Ekert، Chiara Macchiavello، اور Michele Mosca. کوانٹم الگورتھم پر نظرثانی کی گئی۔ لندن کی رائل سوسائٹی کی کارروائی۔ سیریز A: ریاضی، جسمانی اور انجینئرنگ سائنسز، 454(1969):339–354، 1998. doi:10.1098/​rspa.1998.0164.
https://​doi.org/​10.1098/​rspa.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] Kai DeLorenzo، Shelby Kimmel، اور R. Teal Witter. st-Connectivity کے لیے کوانٹم الگورتھم کی ایپلی کیشنز۔ تھیوری آف کوانٹم کمپیوٹیشن، کمیونیکیشن اینڈ کرپٹوگرافی (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/​PhysRevLett.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] مائیکل جیریٹ، سٹیسی جیفری، شیلبی کامل، اور الوارو پیڈرافیٹا۔ کنیکٹیویٹی اور متعلقہ مسائل کے لیے کوانٹم الگورتھم۔ الگورتھم (ESA 26) پر 2018ویں سالانہ یورپی سمپوزیم میں، صفحات 49:1–49:13، 2018. doi:10.4230/​LIPIcs.ESA.2018.49۔
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2018.49

ہے [20] Alexei Y. Kitaev. کوانٹم پیمائش اور ایبیلین سٹیبلائزر کا مسئلہ۔ 1995. arXiv:quant-ph/9511026۔
arXiv:quant-ph/9511026

ہے [21] ٹرائے لی، رجت متل، بین ڈبلیو ریچارڈٹ، رابرٹ اسپالک، اور ماریو شیگیڈی۔ ریاستی تبدیلی کی کوانٹم استفسار کی پیچیدگی۔ 2011 میں کمپیوٹر سائنس کی بنیادوں پر IEEE 52 ویں سالانہ سمپوزیم، صفحہ 344–353، 2011. doi:10.1109/FOCS.2011.75۔
https://​doi.org/​10.1109/FOCS.2011.75

ہے [22] فریڈرک میگنیز، اشون نائک، جیریمی رولینڈ، اور میکلوس سانتھا۔ کوانٹم واک کے ذریعے تلاش کریں۔ SIAM جرنل آن کمپیوٹنگ، 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 کے سالانہ ACM-SIAM سمپوزیم کی کارروائی میں، کارروائی، صفحہ 560-569۔ 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

کی طرف سے حوالہ دیا گیا

[1] سٹیسی جیفری، شیلبی کامل، اور الوارو پیڈرافیتا، "پاتھ ایج سیمپلنگ کے لیے کوانٹم الگورتھم"، آر ایکس سی: 2303.03319, (2023).

[2] Michael Czekanski، Shelby Kimmel، اور R. Teal Witter، "مضبوط اور خلائی موثر دوہری مخالف کوانٹم سوال الگورتھم"، آر ایکس سی: 2306.15040, (2023).

مذکورہ بالا اقتباسات سے ہیں۔ SAO/NASA ADS (آخری بار کامیابی کے ساتھ 2024-04-11 15:45:18)۔ فہرست نامکمل ہو سکتی ہے کیونکہ تمام ناشرین مناسب اور مکمل حوالہ ڈیٹا فراہم نہیں کرتے ہیں۔

On Crossref کی طرف سے پیش خدمت کاموں کے حوالے سے کوئی ڈیٹا نہیں ملا (آخری کوشش 2024-04-11 15:45:17)۔

یہ مقالہ کوانٹم میں کے تحت شائع کیا گیا ہے۔ Creative Commons انتساب 4.0 انٹرنیشنل (CC BY 4.0) لائسنس کاپی رائٹ اصل کاپی رائٹ ہولڈرز جیسے مصنفین یا ان کے اداروں کے پاس رہتا ہے۔

ٹائم اسٹیمپ:

سے زیادہ کوانٹم جرنل