تجارت کمی محاسباتی کوانتومی: الگوریتم داوری آماری با فرکانس بالا

برای تجربه مزایای فرمت پرونده EPUB3 به یک نرم افزار reader یا سازگار نیاز دارید.

1257 بارگیری در کل

این مقاله را به اشتراک بگذارید

نامه الکترونیکی نویسنده

وابستگی های نویسنده

1 Computing Quantum Computing ، Hefei ، جمهوری خلق چین

2 آزمایشگاه کلیدی اطلاعات کوانتومی ، دانشگاه علوم و فناوری چین ، Hefei 230026 ، جمهوری خلق چین

3 موسسه اطلاعات مصنوعی ، مرکز جامع علوم ملی Hefei ، Hefei 230088 ، جمهوری خلق چین

4 مرکز CAS برای تعالی و مرکز نوآوری هم افزایی در اطلاعات کوانتومی و فیزیک کوانتومی ، دانشگاه علوم و فناوری چین ، Hefei 230026 ، جمهوری خلق چین

5 آزمایشگاه ملی Hefei ، دانشگاه علوم و فناوری چین ، Hefei 230088 ، جمهوری خلق چین

یادداشت های نویسنده

6 نویسنده ای که باید به آنها هر مکاتبات پرداخته شود.

شناسه های orcid

تاریخ

1. 19 مارس 2022 دریافت کرد
2. اصلاح شده 28 ژوئن 2022
3. 5 ژوئیه 2022 را پذیرفت
4. منتشر شده 5 اوت 2022

چکیده

تجارت کمی بخشی جدایی ناپذیر از بازارهای مالی با نیازهای سرعت محاسبه بالا است ، در حالی که هنوز هیچ الگوریتم کوانتومی در این زمینه معرفی نشده است. ما الگوریتم های کوانتومی را برای تجارت داوری آماری با فرکانس بالا با استفاده از تخمین شماره زمان متغیر و رگرسیون خطی کوانتومی پیشنهاد می کنیم. پیچیدگی الگوریتم از معیار کلاسیک O (n 2 d) به ، جایی که n طول داده های معاملاتی است ، کاهش یافته است ، و D تعداد سهام است ، κ₀شماره شرط است و دقت مورد نظر است. علاوه بر این ، دو الگوریتم ابزار برای برآورد شماره شرایط و تست ادغام ایجاد شده است.

استناد به صادرات و چکیدهBibtex RIS

محتوای اصلی این کار ممکن است تحت شرایط مجوز Creative Commons Attribution 4. 0 استفاده شود. هرگونه توزیع بیشتر این کار باید نسبت به نویسنده (ها) و عنوان کار ، استناد به ژورنال و DOI حفظ شود.

1. مقدمه

با توسعه سریع محاسبات کوانتومی [1-3] ، Qubits در تراشه ها تا 53 مورد در حال حاضر [3] است و به زودی در نقشه راه سیستم های کوانتومی بر اساس ابررساناتی بیش از 100 گسترش می یابد. از این رو ، محاسبات کوانتومی پتانسیل حل مشکلات عملی مانند شیمی [4-6] ، مواد [7] ، طراحی دارو [8] و غیره را نشان می دهد.

محاسبات کوانتومی اثرات مثبتی در امور مالی ایجاد کرده است [9، 10]، و الگوریتم های کوانتومی کنونی عمدتاً بر حل مسائل قیمت گذاری مشتقات و تحلیل ریسک توسط شبیه سازی کوانتومی مونت کارلو (QMC) [11-16] تمرکز می کنند، و سبد سهام را از طریق دودویی بدون فشار درجه دوم بهینه می کنند. بهینه سازی (QUBO) [17-19]، و کار تجزیه و تحلیل مالی با استفاده از یادگیری ماشین کوانتومی (QML) [20-23]. با این حال، برای معاملات کمی و به ویژه آربیتراژ آماری، هنوز هیچ الگوریتم کوانتومی مربوطه وجود ندارد.

تجارت کمی یک زمینه ضروری از امور مالی است که بر روش های معاملاتی الگوریتمی از طریق مطالعه داده های معاملاتی تاریخی و توسعه الگوریتم معاملاتی پیچیده تمرکز دارد. و آربیتراژ آماری یک رویکرد جریان اصلی معاملات کمی است که توسط اکثر صندوق های تامینی اتخاذ شده است [24، 25]. ایده اصلی آربیتراژ توصیف حرکت از اوراق بهادار و پرتفوی و کسب سود از خطای قیمت گذاری معامله گران دیگر است. در حالی که بسیاری از الگوریتم های کلاسیک برای تجارت کمی پیشنهاد شده اند [26-29]، و تکنیک های سخت افزار سنتی از جمله ارتباطات مادون قرمز و آرایه دروازه قابل برنامه ریزی میدانی در طول سال ها به کار گرفته شده اند [30، 31]، هنوز نیاز به سرعت نمی تواند برآورده شود. پیاده سازی آن روش های آماری پیچیده، به ویژه در وضعیت سریع تر انجام معاملات با فرکانس بالا (HFT) که نیاز به سرعت محاسبات بسیار مهم است [32]. در آربیتراژ آماری، شخص باید از طریق بسیاری از رگرسیون های خطی و آزمون های هم انباشتگی که شامل یک ماتریس عظیم از داده های تاریخی است، یک جفت هم انباشته بالقوه را پیدا کند. به عنوان مثال، در بازارهای سهام ایالات متحده، اندازه مشکل می تواند از N = 10 7 بیشتر شود و پیچیدگی آن 10 15 است (برای جزئیات به بخش 6 مراجعه کنید) که محاسبه آن توسط رایانه های کلاسیک بسیار دشوار است. برای این مشکل، محاسبات کوانتومی ممکن است راه حل موثری ارائه دهد.

در این مقاله ، الگوریتم های کوانتومی اعمال شده برای استراتژی داوری آماری ارائه شده است. این شامل دو زیر مجموعه است: مورد اول الگوریتم انتخاب زمان متغیر (VTPA) است که با احتمال زیاد ، امکان پذیرش بالقوه از اوراق بهادار و پرتفوی را پیدا می کند. مورد دوم الگوریتم تست ادغام کوانتومی (QCTA) است که بر تأیید کارآمد جفت های همبسته متمرکز است ، که در آمار کاملاً ارزشمند است اما قبلاً از طریق محاسبات کوانتومی حاصل نشده است. معیار کلاسیک برای دستیابی به روش پیش انتخاب با فاکتورسازی ماتریس با پیچیدگی O (N 3) [33] است ، در حالی که پیچیدگی الگوریتم ما جایی است که D تعداد سهام معمولاً بسیار کمتر از طول N و κ است.₀شماره شرط استعلاوه بر این ، یک ابزار کارآمد به نام الگوریتم مقایسه شماره کوانتومی (QCNCA) که برای بررسی تعداد وضعیت ماتریس استفاده می شود ، پیشنهاد شده است و می تواند در بسیاری از حوزه های دیگر اعمال شود. تخمین و بهینه سازی در تعداد شرط ، مشکلات واقعی با سیستم های خطی است ، در حالی که تعداد کمی از کار بر روی این موضوع تمرکز دارد.

ساختار این مقاله به شرح زیر است: پس از ارائه بیانیه و تجزیه و تحلیل در بخش 2 ، ساختار جهانی و نتایج اصلی کار ما در بخش 3 نشان داده شده است. جزئیات VTPA و QCT به ترتیب در بخش های 4 و 5 شرح داده شده است.، به دنبال بحث در مورد پیچیدگی و مزیت کوانتومی در بخش 6.

2. مشکل داوری آماری

داوری آماری یک روش معاملاتی خنثی در بازار برای الگوبرداری از دارایی های مختلف و تصحیح خطای قیمت گذاری در بازار است. پیشگام توسط جری بامبرگر [34] ، داوری آماری چیزهای زیادی را توسعه داده است ، و Crux و Core برای مدل سازی این امر هستند. پس از چارچوبی که برای اولین بار توسط Vidyamurthy معرفی شده است [27] ، داوری آماری عمدتاً به سه مرحله کلیدی تقسیم می شود: اولا ، دو یا چند اوراق بهادار که در یک دوره شکل گیری با هم جمع شده اند باید از پیش انتخاب شوند. ثانیا ، برخی از نسخه های تست ادغام Engl e-Granger [35] برای تأیید گرفته شده است. سوم ، گسترش بین آنها در یک دوره معاملاتی بعدی توسط برخی آستانه های بهینه ورود/خروج کنترل می شود. از آنجا که گسترش سهام به میانگین تاریخی آن باز می گردد ، و با اشتیاق اوراق بهادار بیش از حد و کوتاه کردن موارد بیش از حد در همان زمان می توان سود را از رفتار غیر منطقی سایر معامله گران بدست آورد [26] (برای مرجع شکل 1 را ببینید).

شکل 1. تقاطع قیمت های نزدیک تنظیم شده PEP و KO با چند برابر کننده نجات 2. 8. x-axis خط زمانی است و y-axis قیمت را نشان می دهد. خط قرمز دنباله ای از قیمت های نزدیک روزانه PEPSI است ، و خط آبی توالی قیمت نزدیک روزانه Coca-Cola است که توسط یک فاکتور 2. 8 از 8 اوت 2020 تا 8 اوت 2021 ضرب شده است. این عامل از رگرسیون خطی گرفته می شوداز آنجا که مقیاس قیمت متوسط این شرکت ها متفاوت است و به طور مستقیم قابل مقایسه نیست. این تصویر نشان دهنده جمع آوری این دو سهام و استراتژی داوری آماری است: در 2 فوریه 2021 گسترش این سهام به حداکثر افزایش یافته است و ما می توانیم PEP و KO را کوتاه کنیم و سپس آنها را نگه داریم تا اینکه در ژوئیه 2021 معکوس شودو سود کسب کنید.(داده های بازار را می توان از Yahoo! API مالی بارگیری کرد. یک روش پایتونیک برای بارگیری داده های بازار را می توان در وب سایت https://pypi.org/project/yfinance/) یافت.

اولین و سخت مشکل داوری آماری ، یافتن تقاطع دارایی ها است. اگرچه ماتریس کواریانس می تواند برای توصیف همبستگی هر جفت دارایی استفاده شود ، اما بیشتر اوقات برای معامله گران مدل سازی چند قطبی بیش از سه دارایی در بازار را مدل می کند. در آمار ، چند قطبی به وضعیتی اشاره دارد که در آن برخی از متغیرهای توضیحی در یک مدل رگرسیون چندگانه بسیار مرتبط هستند. بیانیه مسئله رسمی به شرح زیر آورده شده است:

Problem 1 (Multicollinear detection problem). Suppose that P = p>مجموعه ای از اوراق بهادار است و مجموعه ای از داده های نقل قول تاریخی سهام است. در اینجا یک عنصر P به عنوان قیمت سهام j در زمان t وجود دارد. ماتریس P از رتبه کاملی برخوردار است زیرا هیچ رابطه خطی کاملی در داده های بازار مالی پر سر و صدا وجود ندارد. هدف این است که تأیید کنیم که آیا چندانی وجود دارد که از نظر آماری از نظر آماری معنی دار است.

روش کلاسیک برای جستجوی چند قطبی با رگرسیون چندگانه است. با این حال ، دو مشکل وجود دارد که یک نفر باید با آن روبرو شوید: اولا پیچیدگی الگوریتم رگرسیون کلاسیک o (n 3) است در حالی که اندازه مسئله واقع بینانه n بسیار بزرگ است. ثانیا ، پیچیدگی الگوریتم به سرعت برای ماتریس نادرست که اغلب در وضعیت چند قطبی ظاهر می شود ، به سرعت افزایش می یابد.

در تجزیه و تحلیل عددی ، برای تشخیص و اندازه گیری جدی بودن مشکل چند قطبی ، شماره وضعیت κ معرفی می شود. با توجه به مشکل F ، به طور کلی اندازه گیری تغییر مقدار خروجی تقسیم شده با تغییر متغیر ورودی x است:

در مورد ماتریس ، تعداد شرایط مرتبط با معادله خطی AX = B وابستگی دقت به داده های ورودی را آزاد کنید. به طور خاص ، تعداد شرایط ماتریس طبیعی A است

باید تأکید کرد که شماره شرط خاصیت خود ماتریس است و به الگوریتم یا صحت رایانه مورد استفاده بستگی ندارد. از این رو ، هر دو رایانه کلاسیک و کوانتومی یک مشکل مشترک برای حل یک سیستم خطی معادلات بدخیم (شماره وضعیت بالا) دارند. هرچه تعداد شرایط بزرگتر باشد ، ماتریس بدتر است و پیچیدگی الگوریتم خیلی سریع افزایش می یابد.

دومین مشکل داوری آماری ، تأیید چند قطعه اوراق بهادار از پیش تعیین شده چند قطبی است. برای سودآوری ، فرض بر این است که قیمت گسترش به میانگین تاریخی آن بازگردد ، که توسط مفهوم آماری چند مرحله ای تضمین می شود. به طور خلاصه ، MultiCointegration یک ترکیب خطی از چندین سری زمانی معین (که به عنوان سری باقیمانده ها مشخص شده است) را ثابت می کند (نه زمان متفاوت) ، و می تواند خاصیت برگشت متغیرها را توصیف کند. با توضیح مفصل مفاهیم آماری ارائه شده در پیوست A ، بیانیه مسئله رسمی:

مشکل 2 (مشکل تست چند قطعه). فرض کنید این مجموعه ای از داده های نقل قول تاریخی سهام است. در اینجا P (j) یک سری زمانی به عنوان قیمت سهام j است. هدف این است که تأیید کنیم که آیا این سریال های زمانی یکپارچه شده اند.

الگوریتم آزمون ادغام کلاسیک از دو روش رگرسیون تشکیل شده است: یکی برای مشتق ضرایب ترکیبی خطی و دیگری برای آزمون فرضیه ثابت زمان است. پیچیدگی هر رگرسیون o (n 3) است.

3. داوری آماری کوانتومی

در این بخش ، دو الگوریتم حل مشکل داوری آماری کوانتومی ارائه شده است. یکی در مورد آستانه شماره شرایط ثابت است. مورد دیگر برای تعداد مشخصی از اوراق بهادار باقی مانده است. با توجه به داده های تاریخی بسیاری از سهام برای یک بازه طولانی ، هدف ما انتخاب سهام هایی است که با هم یکپارچه شده اند. این الگوریتم عمدتاً شامل دو مرحله است: با استفاده از VTPA (P ، κ) که در آن VPTA صحیح است اگر تعداد وضعیت نمونه کارها از آستانه κ بزرگتر باشد ، در آن با استفاده از VTPA (P ، κ) که در آن VPTA صحیح است ، در آن قرار دارد. و سپس تأیید کنید که آیا نمونه کارها از پیش تعیین شده P با اجرای QCT (P) برای خروجی پرچم ادغام F و ضرایب مربوطه β ترکیب می شود.

3. 1بارگیری داده ها

بارگیری داده ها یک روش مهم و دشوار برای الگوریتم های کوانتومی با توجه به کاربرد عملی است. در این زیر بخش ، ساختار داده و روش بارگیری داده می شود و سپس پیچیدگی زمان مورد تجزیه و تحلیل قرار می گیرد. علاوه بر این ، ما ثابت کردیم که این روش کارآمد و بهینه است.

Suppose that P = p>استخر نمونه کارها است و مجموعه ای از داده های نقل قول تاریخی سهام است. در اینجا یک عنصر P به عنوان قیمت سهام j در زمان t وجود دارد. ماتریس P از رتبه کاملی برخوردار است زیرا هیچ رابطه خطی کاملی در داده های بازار مالی پر سر و صدا وجود ندارد. دو الگوریتم آماری کوانتومی در مدل استاندارد اوراکل کار می کنند و ماتریس در یک حافظه دسترسی تصادفی کوانتومی (QRAM) ذخیره می شود [36-38]. یک روش برای انجام نقشه فرض می شود

برای هر j ∈ [1 ، 2 ،. د] و t ∈ [1 ، 2 ،. n] ، و قیمت به عنوان رشته کمی در ثبت سوم ذخیره می شود.

به منظور استخراج ماتریس متقارن واقعی مورد نظر ، استراتژی HHL [39 ، 40] به این صورت اتخاذ شده است:

علاوه بر این ، هنجار ماتریس برای برآورده کردن فرض می شود ||a ||= 1 بدون از دست دادن کلی بودن از آنجا که در غیر این صورت اجازه می دهد.

برای اکثر الگوریتم های کوانتومی در مورد وضعیت واقع گرایانه در مقایسه با الگوریتم های کلاسیک ، بارگیری داده ها یک مشکل رایج و مهم مانند تشخیص الگوی و سیستم توصیه است که در آن بارگیری داده ها یک مشکل تنگنا است زیرا هر تیک داده های زیادی که دارای اطلاعات تصویر هستند بارگیری می شوند [41]با این حال ، برای مورد داده های مالی ، همه چیز بسیار متفاوت است:

برای صحنه مالی مشخص شده ما ، ما تکنیکی را به نام به روزرسانی افزایشی [42 ، 43] اعمال می کنیم ، به طوری که می توان پیچیدگی زمان روش بارگیری داده ها را ثابت کرد. داده ها باید بارگیری شوند به دو بخش تقسیم می شوند: داده های تاریخی و داده های بارگذاری جدید. اگرچه ممکن است زمان بارگیری داده های تاریخی برای اولین بار طولانی باشد ، اما قبل از زمان معاملات به پایان رسیده است. و در هر ثانیه جدید از زمان معاملات ، ماتریس بزرگ داده های تاریخی بدون تغییر است و فقط تعداد مشخصی از خطوط داده به روز می شود. از این رو پیچیدگی به روزرسانی داده ها را می توان به عنوان یک ثابت فرض کرد ، که بسیار متفاوت از سایر الگوریتم های کوانتومی است.

در مقایسه با الگوریتم های کلاسیک ، از آنجا که این روش جدید برای ذخیره سازی داده ها نیز روش تولید داده است ، پیچیدگی زمانی بارگیری داده های کوانتومی الگوریتم ما به همان ترتیب از کلاسیک است. و الگوریتم کوانتومی از روش محاسبات بهره مند می شود.

علاوه بر این ، از آنجا که داده های مبتنی بر معاملات تاریخی تصادفی است ، نمی توان آن را به طور مؤثر از یک مدار کوانتومی طراحی شده بدست آورد. در غیر این صورت داده های تاریخ را می توان کاملاً توسط یک مدار ثابت پیش بینی کرد و این غیرممکن است. این اشاره دارد که هیچ مدار کارآمدتری برای تهیه ماتریس تاریخی به طور مستقیم وجود ندارد و به روزرسانی داده های افزایشی بهینه است.

3. 2الگوریتم شماره شرایط ثابت

در این مورد ، بازار ثابت است و آستانه شماره وضعیت مورد استفاده برای انتخاب می تواند از داده های معاملاتی تاریخی حاصل شود. اگر κ کارآمد باشد₀حاصل از داده های تاریخی به عنوان آستانه فیلتر گرفته شده است ، الگوریتم زیر 1 داده شده است:

الگوریتم 1. الگوریتم داوری آماری کوانتومی با انتخاب شماره وضعیت ثابت.

فرض کنید که ما داده های تاریخی سهام J را با کنه T داریم ، سپس برای هر نمونه کارها P از سهام D ، ما از مدار الگوریتم انتخاب زمان متغیر استفاده می کنیم. این مدار کوانتومی باز می گردد که آیا این تعداد وضعیت ماتریس داده از κ بزرگتر است₀واداین مبتنی بر الگوریتم مقایسه شماره Quantum Number جدید است که می تواند تخمین شماره وضعیت سریع را با محاسبه EigenValue اجرا کند ، و ساختار زمان متغیر برای ایجاد یک اثر شتاب دوم با استفاده از مورد با مورد تعداد زیاد استفاده می شود. اگر نتیجه VTPA درست باشد ، می دانیم که شماره وضعیت ماتریس به اندازه کافی بزرگ است به گونه ای که احتمال بالایی وجود دارد که این نمونه کارها حاوی ستون های چند قلو از توالی قیمت سهام باشد. سپس ما مدار تست ادغام کوانتومی را اعمال خواهیم کرد که می تواند محاسبه کند اگر این نمونه کارها چند قطبی حاوی ترکیبی خطی از سهام باشد که به صورت دلخواه یکپارچه شود.

3. 3الگوریتم شماره شرایط سازگار

در مورد این مورد که بازار مالی به شدت تغییر می کند و آستانه ثابت κ₀را می توان استخراج کرد، یک الگوریتم 2 حتی کارآمدتر ارائه می شود و ایده اصلی او به شرح زیر است: از آنجایی که الگوریتم فرعی پیش انتخاب تک مرحله ای ما را می توان برای هر κ معینی استفاده کرد، یک روش پیش انتخابی κ مترقی را می توان پیاده سازی کرد. ماتریس های پورتفولیو با κ کوچک در چند مرحله اول مستقیماً منسوخ می شوند تا زمانی که تعداد ماتریس های باقی مانده به اندازه کافی کم شود و تا آن زمان، آزمون هم انباشتگی کوانتومی اجرا می شود.

الگوریتم 2. الگوریتم آربیتراژ آماری کوانتومی با پیش انتخاب پیش رونده.

هر دوی دو الگوریتم بالا برای آربیتراژ آماری هستند و انتخاب به بازار خاص بستگی دارد: اگر آستانه κ ثابت باشد، الگوریتم اول انتخاب می شود. در غیر این صورت، دومی ترجیح داده می شود. از آنجایی که دو زیرروال VTPA و QCT پیچیده هستند و الگوریتم فرعی ابزار QCNCA توسعه یافته است، به ترتیب در بخش های 4 و 5 معرفی خواهند شد.

4. پیش انتخاب زمان متغیر

در این بخش، ایده اصلی بخش اول کار خود را به عنوان یک الگوریتم کوانتومی زمان متغیر برای از پیش انتخاب سهامی که چند خطی هستند و در نتیجه ممکن است در صورت لزوم با هم ادغام شوند، توضیح خواهیم داد.

اگرچه ماتریس های بدشرطی معمولاً به عنوان یک مشکل وحشتناک در نظر گرفته می شوند که باید سعی کرد از آن اجتناب کرد، ما ایده اکتشافی را برای تشخیص چند خطی با جستجوی ماتریس هایی با مقادیر ویژه کوچک و اعداد شرط بزرگ توسعه می دهیم. QCNCA برای تعیین اینکه آیا عدد شرط κ یک ماتریس معین بزرگتر از آستانه κ است ایجاد شده است.₀در بخش 4. 1.

از آنجایی که وابستگی QCNCA به κ درجه دوم است، تکنیک الگوریتم کوانتومی زمان متغیر برای تسریع اجرای انتخاب ماتریس ها معرفی شده است [44] و سپس VTPA به شرح زیر است:

قضیه 1. با فرض اینکه بسیاری از سیستم های خطی مختلف با شماره شرط ناشناخته κ و P داده شوند_jاحتمال اینکه عدد شرط κ را برآورده کند را نشان دهید_{j −1}= 2 j −1 ⩽ κ ⩽ κ_j= 2 j. سپس یک الگوریتم کوانتومی کارآمد برای انتخاب ماتریس با شماره شرایط κ ⩾ κ وجود دارد₀وادپیچیدگی متوسط پرس و جو است. در مورد توزیع احتمال یکنواخت ، پیچیدگی پرس و جو برای تعیین اینکه آیا تعداد شرایط بزرگتر از κ است₀.

اثبات صحت و پیچیدگی قضیه 1 به ترتیب در بخش های 4. 3 و 4. 4 آورده شده است.

4. 1ابزارها: الگوریتم مقایسه شماره شرایط کوانتومی

با درک اینکه چند قطبی با κ بزرگ [45 ، 46] و از این رو مقادیر ویژه ای کوچک ظاهر می شود ، الگوریتم انتخاب زیر توسعه می یابد: یک الگوریتم تخمین فاز ساده را تکرار کنید تا یک مقادیر کوچک به اندازه کافی کوچک تشخیص داده شود. اگر چنین مقادیر ویژه ای پیدا شود ، اوراق بهادار مربوطه به عنوان گزینه جایگزین ثبت می شود. شایان ذکر است که ممکن است برخی از جفت های یکپارچه در الگوریتم ما از دست بروند ، اما مهم نیست زیرا وظیفه ما جستجوی برخی از اوراق بهادار خطی به جای مأموریت غیرممکن برای یافتن همه جفت های همخوانی است. ما این روش را نشان می دهیم که مقدار کوانتومی شماره مقایسه کننده QCNC (κ ، φ) است و نتیجه زیر را می گیریم:

LEMMA 2. با فرض اینکه A یک ماتریس N × N Hermitian با ||a ||= 1 با شماره وضعیت ناشناخته κ و عملکرد چگالی احتمال مقادیر ویژه P (λ) است. سپس یک الگوریتم کوانتومی با استفاده از تماس های A وجود دارد تا تعیین کند که آیا تعداد شرایط از κ بزرگتر است₀واددر مورد توزیع احتمال یکنواخت ، تماس های A به گونه ای هستند که هر زمان κ ⩾ 2 κ₀، quit هدف 1 خواهد بود.

باید توجه داشت که این زمان تکرار ، به ویژه هنگامی که κ بزرگ است ، توسط آستانه κ تعیین می شود₀، در حالی که الگوریتم های سنتی به κ ناشناخته بستگی دارند. این یک الگوریتم است که می داند آیا شرط یک سیستم خطی از آستانه داده شده بدون حل معادلات بزرگ است یا خیر.

اثبات لما 2. بدون از دست دادن کلی بودن ، فرض کنید A یک ماتریس با Norm Frobenius است

(در غیر این صورت اجازه دهید) ، و رتبه ناشناخته r. محاسبه مستقیم نشان می دهد که: