গিবস পার্টিশন ফাংশনের জন্য সহজ (শাস্ত্রীয়) এবং দ্রুত (কোয়ান্টাম) অ্যালগরিদম

উত্স নোড: 1648838

শ্রীনিবাসন অরুণাচলম1, Vojtech Havlicek1,2, Giacomo Nannicini1, ক্রিস্তান টেমে1, এবং পাওয়েল Wocjan1

1আইবিএম কোয়ান্টাম, আইবিএম টিজে ওয়াটসন রিসার্চ সেন্টার
2গণিতের স্কুল, ব্রিস্টল বিশ্ববিদ্যালয়

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

বিমূর্ত

আমরা একটি নির্দিষ্ট তাপমাত্রায় ক্লাসিক্যাল হ্যামিলটোনিয়ানদের আনুমানিক পার্টিশন ফাংশনগুলির জন্য ক্লাসিক্যাল এবং কোয়ান্টাম অ্যালগরিদম উপস্থাপন করি। আমাদের কাজের দুটি প্রধান অবদান রয়েছে: প্রথমত, আমরা এর নমুনা জটিলতা উন্নত করতে স্টেফানকোভিক, ভেম্পালা এবং ভিগোডা (জে. এসিএম, 56(3), 2009) এর ক্লাসিক্যাল অ্যালগরিদম পরিবর্তন করি; দ্বিতীয়ত, আমরা এই নতুন অ্যালগরিদম পরিমাপ করি, হ্যারো এবং ওয়েই (SODA 2020) এর কারণে এই সমস্যার জন্য আগের দ্রুততম কোয়ান্টাম অ্যালগরিদমের উন্নতি করে।
পার্টিশন ফাংশন অনুমান করার প্রচলিত পদ্ধতির জন্য তথাকথিত শীতল সময়সূচী গঠনকারী বিপরীত তাপমাত্রার একটি সেটে গিবস বিতরণের উপায়গুলি আনুমানিক করা প্রয়োজন। কুলিং সময়সূচীর দৈর্ঘ্য সরাসরি অ্যালগরিদমের জটিলতাকে প্রভাবিত করে। Huber (Ann. Appl. Probab., 25(2), 2015) এর পেয়ারড-প্রোডাক্ট এস্টিমেটরের সাথে Stefankovic, Vempala এবং Vigoda-এর অ্যালগরিদমের আমাদের উন্নত সংস্করণের সংমিশ্রণ করে, আমাদের নতুন কোয়ান্টাম অ্যালগরিদম পূর্বের পরিচিত থেকে একটি ছোট কুলিং সময়সূচী ব্যবহার করে৷ এই দৈর্ঘ্য স্টেফানকোভিচ, ভেম্পালা এবং ভিগোডা দ্বারা অনুমান করা সর্বোত্তম দৈর্ঘ্যের সাথে মেলে। কোয়ান্টাম অ্যালগরিদম এলোমেলো নমুনার সংখ্যার তুলনায় প্রয়োজনীয় কোয়ান্টাম নমুনার সংখ্যায় একটি দ্বিঘাত সুবিধা অর্জন করে
সর্বোত্তম শাস্ত্রীয় অ্যালগরিদম দ্বারা, এবং এর গণনাগত জটিলতা কোয়ান্টাম নমুনাগুলি তৈরি করতে ব্যবহৃত মার্কভ চেইনের বর্ণালী ফাঁকের উপর চতুর্মুখীভাবে ভাল নির্ভরতা রয়েছে।

পার্টিশন ফাংশন হল গিবস ডিস্ট্রিবিউশনের স্বাভাবিককরণের কারণ। তাদের অনুমান আশ্চর্যজনকভাবে কার্যকর: উপযুক্তভাবে নির্বাচিত হ্যামিলটোনিয়ানের জন্য শূন্য তাপমাত্রার পার্টিশন ফাংশন উদাহরণস্বরূপ গ্রাফের রঙের সংখ্যা বা গ্রাফের সাবগ্রাফের সংখ্যা এনকোড করতে পারে। তাই কোয়ান্টাম অ্যালগরিদম দিয়ে কীভাবে তাদের গণনা উন্নত করা যায় তা বোঝা গুরুত্বপূর্ণ।

এখানে আমরা এই সমস্যার জন্য ক্লাসিক্যাল এবং কোয়ান্টাম অ্যালগরিদম উপস্থাপন করি। আমাদের কাজের দুটি প্রধান অবদান রয়েছে: প্রথমত, আমরা এর নমুনা জটিলতা উন্নত করতে স্টেফানকোভিক, ভেম্পালা এবং ভিগোডা (জে. এসিএম, 56(3), 2009) এর ক্লাসিক্যাল অ্যালগরিদম পরিবর্তন করি; দ্বিতীয়ত, আমরা এই নতুন অ্যালগরিদম পরিমাপ করি, হ্যারো এবং ওয়েই (SODA 2020) এর কারণে এই সমস্যার জন্য আগের দ্রুততম কোয়ান্টাম অ্যালগরিদমের উন্নতি করে।

পার্টিশন ফাংশন অনুমান করার স্বাভাবিক পদ্ধতির জন্য তথাকথিত শীতল সময়সূচী গঠনকারী বিপরীত তাপমাত্রার একটি সেটে গিবস বিতরণের উপায়গুলি আনুমানিক করা প্রয়োজন। কুলিং সময়সূচীর দৈর্ঘ্য সরাসরি অ্যালগরিদমের জটিলতাকে প্রভাবিত করে। Huber (Ann. Appl. Probab., 25(2), 2015) এর পেয়ারড-প্রোডাক্ট এস্টিমেটরের সাথে Stefankovic, Vempala এবং Vigoda-এর অ্যালগরিদমের আমাদের উন্নত সংস্করণের সংমিশ্রণ করে, আমাদের নতুন কোয়ান্টাম অ্যালগরিদম পূর্বের পরিচিত থেকে একটি ছোট কুলিং সময়সূচী ব্যবহার করে৷ এই দৈর্ঘ্য স্টেফানকোভিচ, ভেম্পালা এবং ভিগোডা দ্বারা অনুমান করা সর্বোত্তম দৈর্ঘ্যের সাথে মেলে। কোয়ান্টাম অ্যালগরিদম সেরা ক্লাসিক্যাল অ্যালগরিদম দ্বারা আঁকা এলোমেলো নমুনার সংখ্যার তুলনায় প্রয়োজনীয় কোয়ান্টাম নমুনার সংখ্যায় একটি দ্বিঘাত সুবিধা অর্জন করে এবং এর গণনাগত জটিলতা কোয়ান্টাম উত্পাদন করতে ব্যবহৃত মার্কভ চেইনের বর্ণালী ফাঁকের উপর চতুর্মুখীভাবে ভাল নির্ভরতা রয়েছে। নমুনা

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

। তথ্যসূত্র

[1] ইভোনা বেজাকোভা, ড্যানিয়েল স্টেফানকোভিচ, বিজয় ভি ভাজিরানি এবং এরিক ভিগোদা। স্থায়ী এবং সমন্বিত গণনা সমস্যার জন্য সিমুলেটেড অ্যানিলিং ত্বরান্বিত করা। সিয়াম জার্নাল অন কম্পিউটিং, 37(5):1429–1454, 2008। doi:10.1137/​050644033।
https: / / doi.org/ 10.1137 / 050644033

[2] কার্ট বাইন্ডার এবং ডায়েটার ডব্লিউ হিরম্যান। পরিসংখ্যানগত পদার্থবিজ্ঞানে মন্টে কার্লো সিমুলেশন: একটি ভূমিকা (পদার্থবিজ্ঞানে স্নাতক পাঠ্য)। স্প্রিংগার, 2019।

[3] গিলস ব্রাসার্ড, পিটার হোয়ার, মিশেল মোসকা এবং অ্যালাইন ট্যাপ। কোয়ান্টাম প্রশস্ততা পরিবর্ধন এবং অনুমান। সমসাময়িক গণিত, 305:53–74, 2002।

[4] শৌভানিক চক্রবর্তী, অ্যান্ড্রু এম চাইল্ডস, শিহ-হান হুং, টংইয়াং লি, চুনহাও ওয়াং এবং জিয়াওদি উ। উত্তল বস্তুর ভলিউম অনুমানের জন্য কোয়ান্টাম অ্যালগরিদম। arXiv:1908.03903, 2019।
arXiv: 1908.03903

[5] Guillaume Desjardins, Yoshua Bengio, এবং Aaron C Courville. পার্টিশন ফাংশন ট্র্যাকিং. নিউরাল ইনফরমেশন প্রসেসিং সিস্টেমের অগ্রগতিতে, পৃষ্ঠা 2501-2509। Citeseer, 2011।

[6] মার্টিন ডায়ার এবং অ্যালান ফ্রিজ। উত্তল দেহের আয়তন গণনা করা: একটি ক্ষেত্রে যেখানে এলোমেলোতা সম্ভবত সাহায্য করে। সম্ভাব্য সমন্বয়বিদ্যা এবং এর প্রয়োগ, 44:123-170, 1991।

[7] মার্টিন ডায়ার, অ্যালান ফ্রিজ এবং রবি কান্নান। উত্তল বস্তুর আয়তন আনুমানিক করার জন্য একটি এলোমেলো বহুপদী-সময় অ্যালগরিদম। ACM জার্নাল (JACM), 38(1):1–17, 1991. doi:10.1145/​102782.102783.
https: / / doi.org/ 10.1145 / 102782.102783

[8] অ্যান্ড্রু গেলম্যান এবং জিয়াও-লি মেং। স্বাভাবিকীকরণ ধ্রুবক অনুকরণ: গুরুত্ব স্যাম্পলিং থেকে ব্রিজ স্যাম্পলিং থেকে পাথ স্যাম্পলিং। পরিসংখ্যান বিজ্ঞান, পৃষ্ঠা 163–185, 1998. doi:10.1214/​ss/​1028905934।
https://​doi.org/​10.1214/​ss/​1028905934

[9] পল গ্লাসারম্যান। আর্থিক প্রকৌশলে মন্টে কার্লো পদ্ধতি, ভলিউম 53. স্প্রিংগার সায়েন্স অ্যান্ড বিজনেস মিডিয়া, 2013।

[10] ইয়ান গুডফেলো, ইয়োশুয়া বেঙ্গিও এবং অ্যারন কোরভিল। গভীর জ্ঞানার্জন. MIT প্রেস, 2016। http://​/​www.deeplearningbook.org।
http://​/www.deeplearningbook.org

[11] ইয়াসিন হামুদি এবং ফ্রেডেরিক ম্যাগনিজ। কোয়ান্টাম চেবিশেভের অসমতা এবং প্রয়োগ। Automata, Languages, and Programming (ICALP), ভলিউম 46, পৃষ্ঠা 132:69–1:69, 16. doi:2019/​LIPIcs.ICALP.10.4230-এর 2019.69 তম আন্তর্জাতিক কলোকিয়ামে।
https://​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.69

[12] আরাম ডব্লিউ হ্যারো এবং অ্যানি ওয়াই উই। বেয়েসিয়ান ইনফারেন্স এবং পার্টিশন ফাংশন অনুমান করার জন্য অভিযোজিত কোয়ান্টাম সিমুলেটেড অ্যানিলিং। বিচ্ছিন্ন অ্যালগরিদমের চতুর্দশ বার্ষিক এসিএম-সিয়াম সিম্পোজিয়ামের কার্যপ্রণালীতে, পৃষ্ঠা 193–212, 2020। doi:10.1137/​1.9781611975994.12।
https: / / doi.org/ 10.1137 / 1.9781611975994.12

[13] জিওফ্রে ই হিন্টন, সাইমন ওসিন্ডারো এবং ইয়ে-হোয়াই তেহ। গভীর বিশ্বাস জালের জন্য একটি দ্রুত শেখার অ্যালগরিদম। নিউরাল কম্পিউটেশন, 18(7):1527–1554, 2006. doi:10.1162/​neco.2006.18.7.1527।
https://​doi.org/​10.1162/​neco.2006.18.7.1527

[14] মার্ক হুবার। গিবস ডিস্ট্রিবিউশনের স্বাভাবিকীকরণ ধ্রুবকের জন্য আনুমানিক অ্যালগরিদম। দ্য অ্যানালস অফ অ্যাপ্লাইড প্রোবাবিলিটি, 25(2):974–985, 2015. doi:10.1214/​14-AAP1015।
https://​doi.org/​10.1214/​14-AAP1015

[15] মার্ক হুবার এবং সারাহ স্কট। Bayesian অনুমানের জন্য TPA ব্যবহার করা। Bayesian Statistics, 9:257–282, 2010. doi:10.1093/​acprof:oso/​9780199694587.003.0009।
https: / / doi.org/ 10.1093 / acprof: oso / 9780199694587.003.0009

[16] মার্ক জেরাম এবং অ্যালিস্টার সিনক্লেয়ার। স্থায়ী আনুমানিক. সিয়াম জার্নাল অন কম্পিউটিং, 18(6):1149–1178, 1989. doi:10.1137/​0218077।
https: / / doi.org/ 10.1137 / 0218077

[17] মার্ক আর জেরাম, লেসলি জি ভ্যালিয়ান্ট এবং বিজয় ভি. ভাজিরানি। একটি অভিন্ন বন্টন থেকে সম্মিলিত কাঠামোর এলোমেলো প্রজন্ম। তাত্ত্বিক কম্পিউটার বিজ্ঞান, 43:169 – 188, 1986. doi:10.1016/​0304-3975(86)90174-X.
https:/​/​doi.org/​10.1016/​0304-3975(86)90174-X

[18] ভ্লাদিমির কলমোগোরভ। গিবস পার্টিশন ফাংশনের জন্য একটি দ্রুত আনুমানিক অ্যালগরিদম। 31 তম কনফারেন্স অন লার্নিং থিওরিতে, মেশিন লার্নিং রিসার্চের প্রসিডিংসের 75 ভলিউম, পৃষ্ঠা 228-249। PMLR, 2018।

[19] কিয়াং লিউ এবং আলেকজান্ডার টি. ইহলার। হোল্ডারের অসমতা ব্যবহার করে পার্টিশন ফাংশনকে আবদ্ধ করা। মেশিন লার্নিং, ICML, পৃষ্ঠা 28-849-এর 856তম আন্তর্জাতিক সম্মেলনের কার্যপ্রণালীতে। Omnipress, 2011।

[20] F. Magniez, A. নায়ক, J. Roland, এবং M. Santha. কোয়ান্টাম ওয়াক মাধ্যমে অনুসন্ধান. সিয়াম জার্নাল অন কম্পিউটিং, 40(1):142–164, 2011। doi:10.1137/​090745854।
https: / / doi.org/ 10.1137 / 090745854

[21] অ্যাশলে মন্টানারো। মন্টে কার্লো পদ্ধতির কোয়ান্টাম গতি। রয়্যাল সোসাইটির কার্যপ্রণালী A: গাণিতিক, শারীরিক এবং প্রকৌশল বিজ্ঞান, 471(2181):20150301, 2015।

[22] এলচানান মোসেল এবং অ্যালান স্লি। সাধারণ গ্রাফে ising–gibbs স্যাম্পলারের জন্য সঠিক থ্রেশহোল্ড। অ্যান. Probab., 41(1):294–328, 01 2013. doi:10.1214/​11-AOP737।
https://​doi.org/​10.1214/​11-AOP737

[23] ড্যানিয়েল স্টেফানকোভিচ, সন্তোষ ভেম্পালা এবং এরিক ভিগোদা। অভিযোজিত সিমুলেটেড অ্যানিলিং: নমুনা এবং গণনার মধ্যে একটি কাছাকাছি-অনুকূল সংযোগ। জার্নাল অফ দ্য ACM (JACM), 56(3):1–36, 2009. doi:10.1145/​1516512.1516520।
https: / / doi.org/ 10.1145 / 1516512.1516520

[24] মারিও সেজেডি। মার্কভ চেইন ভিত্তিক অ্যালগরিদমের কোয়ান্টাম স্পিড-আপ। 45 তম বার্ষিক IEEE সিম্পোজিয়ামে কম্পিউটার বিজ্ঞানের ভিত্তি, পৃষ্ঠা 32-41। IEEE, 2004।

[25] জেপি ভ্যালেউ এবং ডিএন কার্ড। মাল্টিস্টেজ নমুনা দ্বারা মুক্ত শক্তির মন্টে কার্লো অনুমান। দ্য জার্নাল অফ কেমিক্যাল ফিজিক্স, 57(12):5457–5462, 1972।

[26] এরিক ভিগোডা। নমুনা রঙের জন্য উন্নত সীমানা। জার্নাল অফ ম্যাথমেটিকাল ফিজিক্স, 41(3):1555–1569, 2000. doi:10.1063/​1.533196।
https: / / doi.org/ 10.1063 / 1.533196

[27] মার্ক ভুফ্রে, সিদ্ধান্ত মিশ্র, আন্দ্রে লোখভ এবং মাইকেল চের্টকভ। মিথস্ক্রিয়া স্ক্রীনিং: আইসিং মডেলের দক্ষ এবং নমুনা-অনুকূল শিক্ষা। নিউরাল ইনফরমেশন প্রসেসিং সিস্টেমের অগ্রগতিতে, পৃষ্ঠা 2595-2603, 2016।

[28] পাওয়েল ওয়াকজান এবং অনুরা আবেয়েসিংহে। কোয়ান্টাম স্যাম্পলিংয়ের মাধ্যমে গতি বাড়ান। শারীরিক পর্যালোচনা A, 78(4):042336, 2008. doi:10.1103/​PhysRevA.78.042336.
https: / / doi.org/ 10.1103 / ফিজারিভা 78.042336

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

[১] প্যাট্রিক র‌্যাল, "ফেজ, শক্তি এবং প্রশস্ততা অনুমানের জন্য দ্রুত সমন্বিত কোয়ান্টাম অ্যালগরিদম", arXiv: 2103.09717.

[২] চেন-ফু চিয়াং, অনির্বাণ চৌধুরী, এবং পাওয়েল ওয়াকজান, "স্পেস-এফিসিয়েন্ট কোয়ান্টাইজেশন মেথড ফর রিভার্সিবল মার্কভ চেইন্স", arXiv: 2206.06886.

[৩] গ্যারেট টি. ফ্লয়েড, ডেভিড পি. ল্যান্ডাউ, ​​এবং মাইকেল আর. গেলার, "ওয়াং-ল্যান্ডাউ স্যাম্পলিংয়ের জন্য কোয়ান্টাম অ্যালগরিদম", arXiv: 2208.09543.

[৪] পাওয়েল ওয়াকজান এবং ক্রিস্টান টেমে, "কোয়ান্টাম মানচিত্রের জন্য সেজেডি ওয়াক ইউনিটারিস", arXiv: 2107.07365.

[৫] প্যাট্রিক রাল এবং ব্রাইস ফুলার, "কোয়ান্টাম সিগন্যাল প্রসেসিং থেকে প্রশস্ততা অনুমান", arXiv: 2207.08628.

উপরের উদ্ধৃতিগুলি থেকে প্রাপ্ত এসএও / নাসার এডিএস (সর্বশেষে সফলভাবে 2022-09-02 12:01:44 আপডেট হয়েছে)। সমস্ত প্রকাশক উপযুক্ত এবং সম্পূর্ণ উদ্ধৃতি ডেটা সরবরাহ না করায় তালিকাটি অসম্পূর্ণ হতে পারে।

On ক্রসরেফ এর উদ্ধৃত পরিষেবা উদ্ধৃতি রচনার কোনও ডেটা পাওয়া যায় নি (শেষ চেষ্টা 2022-09-02 12:01:43)।

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

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