hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
자동 시험 장비 테스트 장비 플랫폼
USB는 키보드 및 마우스와 같은 주변 장치를 PC에 연결한다. USB는 단일 포트에 최대 127개의 장치를 처리할 수 있는 플러그 앤 플레이 버스이며, 이론상 최대 처리량은 480 Mbit/s(USB 2.0 사양으로 정의된 고속 USB)이다. USB 포트는 PC의 표준 기능이므로 기존 직렬 포트 기술의 자연스러운 진화이다. 그러나 USB 케이블은 산업용 등급이 아니며, 노이즈에 민감하고, 우발적으로 분리될 수 있으며, 컨트롤러와 장치 사이의 최대 거리는 30m이므로 여러 가지 이유로 산업용 테스트 및 측정 시스템 구축에 널리 사용되지 않는다. RS-232와 마찬가지로 USB는 견고한 버스 연결이 필요하지 않은 실험실 환경의 애플리케이션에 유용하다.
RS-232는 분석 및 과학 기기뿐만 아니라 프린터와 같은 주변 장치 제어에도 널리 사용되는 직렬 통신 사양이다. GPIB와 달리 RS-232 인터페이스로는 한 번에 하나의 장치만 연결하고 제어할 수 있다. RS-232는 또한 일반적으로 20KB/s 미만의 데이터 전송률을 가진 비교적 느린 인터페이스이다. RS-232는 더 느리고 견고하지 않은 연결과 호환되는 실험실 애플리케이션에 가장 적합하다. ±24볼트 전원으로 작동한다.
경계 스캔은 IC의 핀을 제어하고 테스트 대상(UUT)에 대한 연속성(상호 연결) 테스트와 논리 장치 또는 장치 그룹에 대한 기능 클러스터 테스트를 용이하게 하기 위해 PCB 수준 또는 시스템 수준 인터페이스 버스로 구현될 수 있다. 또한 IC 자체에 내장될 수 있는 다른 계측(IEEE 1687 참조) 또는 외부 제어 가능한 테스트 시스템의 일부인 계측을 위한 제어 인터페이스로도 사용될 수 있다.
가장 최근에 개발된 테스트 시스템 플랫폼 중 하나는 온보드 테스트 스크립트 프로세서와 고속 버스를 갖춘 계측기를 사용한다. 이 접근 방식에서 하나의 "마스터" 계측기는 고속 LAN 기반 트리거 동기화 및 장치 간 통신 버스를 통해 연결된 테스트 시스템의 다양한 "슬레이브" 계측기 작동을 제어하는 테스트 스크립트(작은 프로그램)를 실행한다. 스크립팅은 스크립트 언어로 프로그램을 작성하여 일련의 동작을 조정하는 것이다.
이 접근 방식은 테스트 및 측정 애플리케이션의 특징인 작은 메시지 전송에 최적화되어 있다. 네트워크 오버헤드가 거의 없고 100Mbit/초 데이터 전송률을 제공하여 실제 애플리케이션에서 GPIB 및 100BaseT 이더넷보다 훨씬 빠르다.
이 플랫폼의 장점은 연결된 모든 장비가 하나의 밀접하게 통합된 다중 채널 시스템처럼 작동하여 사용자가 필요한 채널 수를 비용 효율적으로 맞추기 위해 테스트 시스템을 확장할 수 있다는 점이다. 이러한 유형의 플랫폼에 구성된 시스템은 마스터 장치가 소싱, 측정, 합격/불합격 결정, 테스트 시퀀스 흐름 제어, 분류 및 구성 요소 핸들러 또는 프로버를 제어하는 완전한 측정 및 자동화 솔루션으로 독립적으로 작동할 수 있다. 전용 트리거 라인 지원은 이 고속 버스로 연결된 온보드 테스트 스크립트 프로세서를 갖춘 여러 장비 간의 동기화된 작업을 추가 트리거 연결 없이 달성할 수 있음을 의미한다.
패러독스 (데이터베이스)
패러독스(Paradox)는 현재 코렐 코퍼레이션에서 발행하는 관계형 데이터베이스 관리 시스템이다.
이 소프트웨어는 원래 Ansa 소프트웨어에서 MS-DOS용으로 출시되었고, 그 회사를 인수한 볼랜드에서 업데이트했다. 1991년 중반, 볼랜드는 애슈턴-테이트와 경쟁 DBASE 제품군을 인수하는 절차를 시작했다. 윈도우 버전은 1992년 볼랜드에서 출시될 예정이었으나, 마이크로소프트의 윈도우용 액세스가 출시될 때까지인 1993년 1월로 연기되었다. 마지막 업데이트는 2009년이었다.
패러독스 (데이터베이스) DOS용 패러독스
DOS용 패러독스는 리처드 슈워츠와 로버트 쇼스탁이 처음 작성하여 1985년 그들의 벨몬트 캘리포니아 기반 회사 Ansa 소프트웨어에서 출시한 관계형 데이터베이스 관리 시스템이다.
뉴욕 타임스는 이 소프트웨어를 "인공지능 기술을 광범위하게 사용하는 떠오르는 소프트웨어 세대 중 하나"로 묘사했으며, 패러독스가 경쟁사인 애슈턴 테이트의 DBASE 파일을 읽을 수 있다는 점을 언급했다.
1987년 9월, 볼랜드는 Paradox/DOS 2.0 소프트웨어를 포함한 Ansa 소프트웨어를 인수했다. 주목할 만한 고전 버전은 3.5와 4.5였다. 3.5 버전까지는 1.0의 진화형이었다. 4.0 및 4.5 버전은 볼랜드 C++ 윈도잉 툴킷으로 재정비되었고 다른 연속 확장 메모리 접근 방식을 사용했다.
패러독스 (데이터베이스) DOS용 패러독스
Paradox/DOS는 1980년대 후반과 1990년대 초반에 성공적인 DOS 기반 데이터베이스였다. 그 당시에는 DBASE와 그 xBase 클론 (폭스프로, 클리퍼)이 시장을 지배했다. 다른 주목할 만한 경쟁자로는 클라리온, DataEase, R:Base, DataFlex가 있었다.
Paradox/DOS를 구별하는 특징은 다음과 같다.
MS-DOS 에뮬레이터로는 dbDOS (유료 제품)와 https://www.vdos.info/ (프리웨어 옵션 제공)가 있으며, 둘 다 Windows Vista 이상 64비트 운영 체제에서 DOS용 Paradox 애플리케이션 (예: DOS용 Paradox 4.5)을 실행할 수 있는 기능을 제공한다.
패러독스 (데이터베이스) 윈도우용 패러독스
윈도우용 패러독스는 DOS용 패러독스와 명확히 다르며, 다른 프로그래머 팀에 의해 제작되었다. 윈도우용 패러독스 애플리케이션은 ObjectPAL이라는 다른 프로그래밍 언어로 프로그래밍된다. DOS 제품의 핵심 기능인 QBE와 데이터베이스 엔진은 DOS 코드를 유지한 포트였지만, PAL에서 ObjectPAL로의 호환성이 크게 깨졌고, 양식 및 보고서의 GUI 디자인 메타포로 전환되었다. ObjectPAL 변경은 논란이 많았지만, PAL이 윈도우에는 해당되지 않는 키 입력 기록 동작을 기반으로 했기 때문에 강제되었다. 키 입력 기록 대신 하이퍼카드의 아이디어를 기반으로 한 객체 기반 언어가 사용되었다. 양식 및 보고서 디자이너는 상세한 레이아웃을 위해 확대/축소 모드에서 작업할 수 있는 기능을 포함하여 장치 독립적인 크기 조절을 사용했다. 마우스 오른쪽 클릭은 제록스 알토와 스몰토크에서 영감을 받아 현재 거의 모든 윈도우 프로그램에서 보편적으로 사용되는 방식으로 양식 및 보고서 속성에 접근하는 데 사용되었다. ObjectPAL은 (하이퍼카드처럼) 시각적 객체와 관련되어 있었으며, 오른쪽 클릭으로도 드러났다. 속성 검사 및 레이아웃 도구는 NeXT에서 빌려온 아이디어로 "고정"되어 화면에 유지될 수 있었으며, 현재 윈도우에서 꽤 널리 채택되었다.
패러독스 (데이터베이스) 윈도우용 패러독스
개발 초기 약 1년 동안 객체 지향 코드는 매크로의 도움을 받아 C로 작성되었고, 터보 C++가 출시되면서 나머지 코드 부분은 C++로 작성되었다. 버전 1.0 출시 전까지 제품 관리자는 조 던컨이었다. 개발 및 QA 팀은 총 약 30명이었다.
윈도우용 패러독스와 밀접하게 관련된 프로젝트인 윈도우용 쿼트로 프로는 모두 1990년 봄, 윈도우 3.0의 베타 버전에서 개발을 시작했다. 윈도우용 패러독스는 원래 계획보다 약 1년 지연되어 1993년 초에 출시되었다. 그 이유는 많았지만, 본질적으로 첫 번째 버전 운영 체제에서 새로운 도구를 사용하여 GUI 패러다임으로 전환하는 대규모 재작성에 객체 지향 언어를 사용하는 것은 전혀 놀라운 일이 아니었다. 그럼에도 불구하고 이는 회사에 큰 문제였고, 마이크로소프트는 윈도우용 패러독스보다 몇 달 먼저 Access를 출시하여 마이크로소프트에 큰 마케팅 승리를 안겨주었다.
패러독스 (데이터베이스) 윈도우용 패러독스
1990년, 볼랜드는 어셈블러로 작성된 DOS 및 윈도우용 내부 DBASE 클론 개발을 시작했으며, 이는 1992년에 출시될 예정이었다. 1992년 초, 애슈턴-테이트가 제품의 윈도우 버전 개발에 어려움을 겪고 있다는 것이 분명해졌고, 볼랜드는 계획을 변경하여 회사를 인수하고 내부 프로젝트를 공식적인 후속작으로 지정했다. 애슈턴-테이트 인수에는 인터베이스 rdbms가 포함되었고, Paradox/W가 Paradox 엔진뿐만 아니라 InterBase와도 함께 작동할 수 있어야 한다고 결정되었으며, 이는 InterBase를 중심으로 하는 IDAPI 엔진의 탄생으로 이어졌다.
인수는 또한 초점을 바꾸었다. 패러독스는 역사적으로 일부 시장에서 DBASE와 경쟁했으며, Paradox/W는 원래 개발자 중심 시장에서 경쟁력을 향상시키기 위해 설계되었다. DBASE가 인수된 후, 이는 더 이상 바람직하지 않았고, 사용 용이성 시장으로 초점이 전환되었다. 그러나 제품은 그 늦은 단계에서 이러한 초점에 맞게 변경될 수 없었으므로 (이는 이후 릴리스에서 발생했다) 제품이 초급 시장에는 다소 과도하게 복잡해졌다.
패러독스 (데이터베이스) 윈도우용 패러독스
마이크로소프트의 첫 번째 데스크톱 데이터베이스 프로그램인 마이크로소프트 액세스는 동일한 시장을 잘 공략했으며, 1992년 11월 COMDEX에서 첫 선을 보였을 때 먼저 출시되었다. 볼랜드의 애슈턴-테이트 인수에 대응하여 마이크로소프트는 폭스프로를 인수하고 그 Rushmore 기술을 Access Jet Engine에 통합하여 성능을 크게 향상시켰다.
마이크로소프트 액세스는 최종 사용자 및 개발자가 구현하기 더 쉬운 많은 기능을 제공했다. 여기에는 QBE에서 Paradox의 필드 텍스트 태그 지정 대신 Windows의 필드 간 링크를 사용하는 더 직관적인 질의 인터페이스와 ObjectPAL보다 PAL과 더 유사한 Access Basic 프로그래밍 언어가 포함되었다. Access와 Paradox는 질의 결과 표시 방식에서 크게 달랐다. Access는 질의가 완료되기 전에도 레코드를 표시했고 출력 테이블 생성에 따른 오버헤드가 없었다. Paradox는 모든 레코드가 검색되고 ANSWER 테이블이 생성된 후에만 결과를 표시했다. 이러한 성능 차이는 대규모 데이터 세트에서 중요했으며 Paradox/W에 부정적인 영향을 미쳤다.
패러독스 (데이터베이스) 윈도우용 패러독스
볼랜드의 저가형 쿼트로 프로 스프레드시트가 마이크로소프트 엑셀에 대항하여 출시된 것을 본받아,
마이크로소프트 액세스는 99달러 가격으로 첫 선을 보였다. 이는 Paradox DOS, Paradox Windows, DBASE의 전통적인 DBMS 가격인 약 799달러를 밑돌았으며, 이는 다른 어떤 회사보다 볼랜드에 부정적인 영향을 미쳤다.
패러독스 (데이터베이스) 윈도우용 패러독스
볼랜드 경영진은 데스크톱 데이터베이스 시장의 85% 점유율을 가지고 있었음에도 불구하고 마이크로소프트와 마이크로소프트 액세스의 위협을 심각하게 과소평가했다. 그럼에도 불구하고 Paradox/W는 한동안 잘 팔렸다. 한편, 볼랜드는 애슈턴-테이트 인수와 관련하여 심각한 문제를 겪고 있었다. 많은 제품 라인이 단종되었고, 기업 재편 및 통합은 고통스러웠으며, 심지어 인수 근거의 핵심이었던 내부 DBASE 프로젝트는 기술적인 이유로 결국 취소되어 볼랜드는 매출 감소와 급히 윈도우용 DBASE를 개발해야 할 심각한 필요성을 겪게 되었다. 볼랜드는 다양한 제품에 필요한 여러 마케팅 전투를 치를 힘을 잃었다. 회사는 DBASE의 대체품을 기다리기로 결정했기 때문에 Paradox는 개발자들에게 최소한으로만 마케팅되었고, 이는 결국 1994년에 출시되었지만 회사에는 너무 늦었다.
패러독스 (데이터베이스) 윈도우용 패러독스
설상가상으로, DOS용 DBASE 클론(FoxBase)은 DBASE를 거의 그대로 복사했지만, 이 제품의 윈도우 버전은 기존의 윈도우용 DBASE 모델 없이 개발되었다. DOS용 DBASE의 강점 중 하나는 다중 공급업체 지원이었는데, 이는 다양한 윈도우 xBase 제품에서 사라졌다. 볼랜드의 윈도우용 비주얼 DBASE는 마이크로소프트의 윈도우용 Foxbase 프로그램을 실행할 수 없었고 그 반대도 마찬가지였다. 파편화된 시장과 윈도우의 이점을 활용하기 위해 프로그램을 다시 작성해야 하는 상황에 직면하자, xBase 사용자들은 DOS에 사용했던 브랜드에 충성할 유인이 거의 없었다.
1995년, 마이크로소프트는 Access를 워드, 엑셀, 파워포인트와 함께 마이크로소프트 오피스 프로페셔널 스위트에 번들로 제공했다. 이는 독립형 제품에 대한 최종 사용자 데스크톱 데이터베이스 시장을 효과적으로 죽였다.
초급 사용자를 위한 사용 편의성 개선을 포함한 견고한 후속 버전에도 불구하고 Paradox는 시장에서 사라졌다. 이는 볼랜드 제품이 워드퍼펙트에 매각될 때 포함되었고, 워드퍼펙트가 금융 제품에 진출하면서 다시 재판매되었다. 작성 시점 현재, 윈도우용 Paradox, 워드퍼펙트, 윈도우용 쿼트로 프로는 모두 코렐 소유이며 그들의 오피스 스위트의 일부로 판매된다. 윈도우용 DBASE는 윈도우 시장에서 중요한 역할을 하기에는 너무 늦게 출시되었다. 그 무렵 대부분의 DBASE 프로그래머들은 매우 유사한 데이터베이스 도구인 마이크로소프트 FoxBASE로 이주했다. 볼랜드 자체는 InterBase/IDAPI 서버를 보유하고 델파이 도구에 노력을 집중했으며, 이는 수년간 데이터 지향 개발자 시장에서 영향력은 작지만 중요한 부분을 차지하게 했다.
패러독스 (데이터베이스) 패러독스 엔진
패러독스 엔진은 DOS 프로그래머가 패러독스 데이터베이스를 사용할 수 있게 하는 미리 컴파일된 C 라이브러리였다. 마이크로소프트 퀵 C 및 터보 C 버전에서 사용할 수 있었다. 소스 코드는 공개되지 않았지만, 라이브러리에 포함된 모든 함수는 잘 문서화되어 있었다.
패러독스 (데이터베이스) 코렐 패러독스
코렐은 1990년대 중반 패러독스를 개발하고 마케팅할 수 있는 특정 권한을 획득했으며, 1997년 코렐 패러독스 8을 출시했다.
패러독스는 코렐의 워드퍼펙트 오피스 스위트의 프로페셔널 버전에도 번들로 제공되었다. 이후 릴리스에는 오피스 프로페셔널 에디션 버전 9, 10, 11, 12, X3, X4, X5, X6, X7, X8, X9, 그리고 2020이 포함되었다. 그러나 2009년 X4용 패러독스 핫픽스 1 이후로는 업데이트되지 않았다. 모든 후속 릴리스는 11.0.0.676의 동일한 버전을 사용한다.
패러독스 (데이터베이스) 사용자
강력한 패러독스 사용자 기반이 있으며, 주로 Paradox 커뮤니티와 그 관련 뉴스그룹을 중심으로 한다. 2024년 7월 30일, 래리 디지오바니는 pnews.thedbcommunity.com 서버가 결국 읽기 전용이 되었다가 완전히 폐쇄될 것이며, TheDBCommunity라는 구글 그룹으로 대체될 것이라고 커뮤니티에 발표했다.
윈도우용 패러독스의 프로그래밍 언어인 ObjectPAL의 많은 팬이 있지만, PAL/DOS 스크립트는 쉽게 마이그레이션할 수 없었다. 객체 및 이벤트 모델이 완전히 달랐기 때문에 PAL을 사용하는 개발자들은 데이터베이스 애플리케이션을 완전히 다시 작성해야 했다.
패러독스 (데이터베이스) 반응
1989년 BYTE는 패러독스 3의 사전 출시 베타 버전을 평가하면서 DBASE 클론이 아니면서도 "DBASE IV를 추월할 잠재력이 있다"고 말했다. 이 잡지는 패러독스가 "가장 고급 애플리케이션에 필요한 모든 기능을 갖추고 있으면서도 경쟁사와 달리 사용하기 쉬웠다"고 언급했다.
컴퓨터 인텔리전스는 1987년에 Ansa가 포춘 1000 PC 데이터베이스 시장의 3%를 차지하여 애슈턴-테이트와 Microrim에 이어 공동 3위라고 추정했다. 1990년 미국공인회계사협회 회원 설문조사에서는 응답자의 5%가 Paradox를 데이터베이스로 사용하고 있음을 발견했다.
알렘빅
알렘빅(alembic, 아랍어: الإنبيق al-inbīq[*], 고대 그리스어: ἄμβιξ ambix[*]에서 유래한 '컵, 비커'라는 뜻)은 액체를 증류하는 데 사용되는, 튜브로 연결된 두 개의 용기로 구성된 연금술 증류기이다.
알렘빅 설명
완전한 증류 장치는 세 부분으로 구성된다.
또 다른 증류 용기인 레토르트의 경우 "캡"과 "쿠커빗"이 결합하여 하나의 용기를 형성한다. 안빅은 쿠커빗의 라스(아랍어 라스 raʾs는 "머리"를 의미한다)라고도 불린다. 쿠커빗의 액체는 가열되거나 끓여지며, 증기는 안빅으로 올라가 벽과 접촉하여 냉각되고 응축되어 주둥이를 통해 수신기로 흘러 들어간다. 알렘빅의 현대적 후손은 증류주를 생산하는 데 사용되는 포트 스틸이다.
알렘빅 역사
디오스코리데스의 약물에 대하여(기원후 약 50년)에 묘사된 그의 암빅스(ambix)는 응축된 수은을 모으는 헬멧 모양의 뚜껑이다. 아테나이오스(기원후 약 225년)에게는 병이나 플라스크였다. 후대 화학자들에게는 조악한 증류 장치의 다양한 부분을 의미했다.
알렘빅 그림은 연금술사 클레오파트라(3세기), 파노폴리스의 조시모스(기원후 약 300년), 시네시우스(기원후 약 373년 ~ 약 414년)의 작품에 등장한다. 두 개의(디비코스) 또는 세 개의(트리비코스) 수신기를 가진 알렘빅이 있었다. 파노폴리스의 조시모스에 따르면, 알렘빅은 유대인 마리아가 발명했다.
안빅은 이븐 알-아왐의 키탑 알-필라하 (농업서)에 묘사되어 있는데, 그는 장미수가 어떻게 증류되는지 설명한다. 그 외에도 콰리즈미의 마파티흐 알-울룸 (과학의 열쇠)과 알-라지의 키탑 알-아스라르 (비밀의 책)에 언급되어 있다. 게버의 저작으로 알려진 라틴어 번역본에는 몇 가지 삽화가 실려 있다.
알렘빅 유니코드
유니코드 문자 집합은 알렘빅에 대한 세 가지 기호를 지정한다. 그림문자 ⚗ (U+2697), 그 이모지 변형 ⚗️ (U+2697U+FE0F), 그리고 고대 연금술 기호 🝪 (U+1F76A)이다.
알렘빅 (컴퓨터 그래픽스)
알렘빅(Alembic)은 소니 픽처스 이미지워크스와 인더스트리얼 라이트 & 매직이 개발한 컴퓨터 그래픽스 파일 형식이다. 이 형식은 2011년 SIGGRAPH에서 발표되었고, 시각 효과 및 애니메이션 전문가들 사이에서 업계 전반에 걸쳐 널리 채택되었다.
주요 초점은 동일한 샷이나 동일한 자산에서 작업하는 여러 그룹 간에 애니메이션된 지오메트리(모델)를 효율적으로 교환하는 것이다. 이들은 서로 다른 애플리케이션을 사용할 수도 있다. 종종 같은 회사나 다른 스튜디오의 다른 부서가 동일한 프로젝트를 작업한다. Alembic은 폴리곤 메시, 서브디비전 서피스, 매개변수 곡선, NURBS 패치 및 입자를 포함하여 업계에서 사용되는 일반적인 지오메트리 표현을 지원한다. Alembic은 또한 변환 계층 및 카메라를 지원한다. 최신 버전에는 재료 및 조명에 대한 초기 지원도 포함된다. Alembic은 특히 절차적 도구의 복잡한 종속성 그래프를 저장하는 데 초점을 맞추지 않고, 애니메이션 장면의 타임라인을 따라 여러 지점에서 모델 데이터를 샘플링하여 "구운" 결과를 저장한다.
양방향 탐색
양방향 탐색(Bidirectional search)은 유향 그래프에서 초기 꼭짓점에서 목표 꼭짓점까지의 최단 경로를 찾는 그래프 탐색 알고리즘이다. 이는 두 가지 동시 탐색을 실행하는데, 하나는 초기 상태에서 앞으로 진행하고 다른 하나는 목표에서 뒤로 진행하여 두 탐색이 만날 때 중지한다. 이 접근 방식의 이유는 많은 경우 더 빠르기 때문이다. 예를 들어, 두 탐색이 모두 분기 인자 b를 가진 트리를 확장하고 시작점에서 목표까지의 거리가 d인 탐색 문제 복잡성의 단순화된 모델에서, 두 탐색 각각은 O(bd/2)의 복잡도(큰 O 표기법 참조)를 가지며, 이 두 탐색 시간의 합은 시작점에서 목표까지의 단일 탐색에서 발생하는 O(bd) 복잡도보다 훨씬 적다.
앤드루 골드버그 외 다수는 데이크스트라 알고리즘의 양방향 버전에서 올바른 종료 조건을 설명했다.
양방향 탐색
A* 탐색과 마찬가지로 양방향 탐색은 목표까지의 남은 거리(정방향 트리) 또는 시작점부터의 거리(역방향 트리)에 대한 휴리스틱 추정치에 의해 안내될 수 있다.
이라 폴은 양방향 휴리스틱 탐색 알고리즘을 설계하고 구현한 최초의 인물이었다. 시작 노드와 목표 노드에서 발생하는 탐색 트리가 해법 공간의 중간에서 만나지 못했다. 드 샹포의 BHFFA 알고리즘이 이 결함을 해결했다.
허용 가능한 휴리스틱을 사용하는 단방향 A* 알고리즘에 의해 발견된 해법은 최단 경로 길이를 가지며, 드 샹포가 설명한 BHFFA2 양방향 휴리스틱 버전도 동일한 속성을 가진다. BHFFA2는 BHFFA보다 더 신중한 종료 조건을 가진다.
양방향 탐색 설명
양방향 휴리스틱 탐색은 특정 상태 에서 다른 상태 로의 상태 공간 탐색이며, 에서 로, 그리고 에서 로 동시에 탐색한다. 이는 에 적용하면 를 얻을 수 있는 유효한 연산자 목록을 반환한다.
역방향 탐색을 위해 연산자가 가역적이어야 하는 것처럼 보일 수 있지만, 주어진 노드 에 대해, 각 부모 노드에서 으로 가는 유효한 연산자가 존재하는 의 부모 노드 집합을 찾을 수 있는 것만 필요하다. 이는 종종 경로 찾기 영역에서 일방통행 도로에 비유된다. 즉, 양방향으로 이동할 수 있을 필요는 없지만, 도로의 끝에 서 있을 때 도로의 시작을 가능한 경로로 결정하는 것이 필요하다.
마찬가지로, 역방향 아크(즉, 양방향으로 가는 아크)가 있는 엣지의 경우 각 방향의 비용이 같을 필요는 없다. 역방향 탐색은 항상 역비용(즉, 정방향 아크의 비용)을 사용한다. 더 공식적으로, 이 부모 를 가진 노드라면, 는 에서 까지의 비용으로 정의된다.
양방향 탐색 설명
탐색 트리의 분기 인자
노드 에서 노드 으로 이동하는 데 관련된 비용
루트에서 노드 까지의 비용
노드 과 목표 사이의 거리에 대한 휴리스틱 추정치
시작 상태
목표 상태 (때때로 로 표시되지만 함수와 혼동하지 말 것)
현재 탐색 방향. 관례상 는 정방향의 경우 1, 역방향의 경우 2이다
반대 탐색 방향 (즉, )
방향 d의 탐색 트리. 이면 루트는 이고, 이면 루트는 이다.
의 리프 (때때로 라고도 함). 이 집합에서 확장을 위한 노드가 선택된다. 양방향 탐색에서는 이를 탐색 '프론티어' 또는 '파면'이라고 부르기도 하는데, 탐색이 그래픽으로 표현될 때 나타나는 방식 때문이다. 이 비유에서, 확장 단계 중 한 파면의 노드가 반대 파면에서 후계자를 가지는 것으로 발견될 때 '충돌'이 발생한다.
의 비리프 노드. 이 집합에는 탐색에 의해 이미 방문된 노드가 포함된다.
양방향 탐색 양방향 휴리스틱 탐색 접근 방식
양방향 알고리즘은 크게 세 가지 범주로 나눌 수 있다: 프론트 투 프론트, 프론트 투 백(또는 프론트 투 엔드), 그리고 경계 탐색. 이들은 휴리스틱을 계산하는 데 사용되는 함수가 다르다.
프론트 투 백 알고리즘은 노드 의  값을 과 반대 탐색 트리의 루트인  또는  사이의 휴리스틱 추정치를 사용하여 계산한다.
프론트 투 백은 세 가지 범주 중 가장 활발하게 연구되는 분야이다. 2004년 현재, 현재 가장 좋은 알고리즘(최소한 15-퍼즐 영역에서)은 BiMAX-BS*F 알고리즘이다.
프론트 투 프론트 알고리즘은 노드 n의 h 값을 n과 의 일부 부분 집합 사이의 휴리스틱 추정치를 사용하여 계산한다. 전형적인 예는 BHFFA(양방향 휴리스틱 프론트 투 프론트 알고리즘)이다. 여기서 h 함수는 현재 노드와 반대쪽 프론트의 노드들 사이의 모든 휴리스틱 추정치 중 최소값으로 정의된다. 또는 공식적으로:
양방향 탐색 양방향 휴리스틱 탐색 접근 방식
여기서 는 노드 n과 o 사이의 거리에 대한 허용 가능한(즉, 과대평가하지 않는) 휴리스틱 추정치를 반환한다.
프론트 투 프론트는 지나치게 많은 계산을 요구한다는 단점이 있다. 노드 n이 열린 목록에 들어갈 때마다 해당  값을 계산해야 한다. 이는 위에서 설명한 대로 n에서 반대쪽 OPEN 집합의 모든 노드까지의 휴리스틱 추정치를 계산하는 것을 포함한다.  b > 1인 모든 영역에서 OPEN 집합의 크기는 기하급수적으로 증가한다.
양자 상태 비소거 정리
물리학에서 양자 상태 비소거 정리(No-deleting theorem)는 양자 정보 이론의 불가능 정리로, 일반적으로 임의의 양자 상태의 두 복사본이 주어졌을 때 그 복사본 중 하나를 삭제하는 것은 불가능하다는 것을 명시한다. 이것은 임의의 상태를 복사할 수 없다는 것을 명시하는 복제 불가능성 정리의 시간 역전된 쌍대이다. 이것은 아룬 K. 파티와 새뮤얼 L. 브라운스타인에 의해 증명되었다. 직관적으로, 이는 정보가 유니터리 진화 하에 보존되기 때문이다.
이 정리는 놀랍게 보이는데, 여러 면에서 양자 상태는 깨지기 쉽기 때문이다; 이 정리는 특정 경우에 양자 상태가 또한 견고하다는 것을 주장한다.
양자 상태 비소거 정리는 복제 불가능성 정리와 함께 범주론의 관점에서 양자 역학의 해석을 뒷받침하며, 특히 대거 대칭 단일 범주로 해석한다. 범주형 양자 역학으로 알려진 이 공식화는 결국 양자 역학에서 선형 논리로의 연결을 양자 정보 이론의 논리로서 가능하게 한다 (고전 논리가 데카르트 닫힌 범주에 기초를 둔 것과 정확히 유사하게).
양자 상태 비소거 정리 개요
알 수 없는 양자 상태의 두 복사본이 있다고 가정하자. 이 맥락에서 중요한 질문은 두 개의 동일한 복사본이 주어졌을 때 양자 역학적 연산을 사용하여 그 중 하나를 삭제하는 것이 가능한가 하는 것이다. 불가능한 것으로 밝혀졌다. 양자 상태 비소거 정리는 양자역학의 선형성의 결과이다. 복제 불가능성 정리와 마찬가지로 이것은 양자 컴퓨팅, 양자 정보 이론 및 일반적인 양자역학에 중요한 의미를 가진다.
양자 삭제 과정은 입력 포트에서 임의의 알 수 없는 양자 상태의 두 복사본을 받아들이고 원본과 함께 빈 상태를 출력한다. 수학적으로 이것은 다음과 같이 설명될 수 있다.
여기서 는 유니터리 연산자, 는 알 수 없는 양자 상태, 는 빈 상태, 는 삭제 기계의 초기 상태이고 는 기계의 최종 상태이다.
고전적인 비트는 복사하고 삭제할 수 있으며, 직교 상태의 큐비트도 마찬가지이다. 예를 들어, 두 개의 동일한 큐비트 와 가 있다면, 우리는 이를 와 로 변환할 수 있다. 이 경우 두 번째 복사본을 삭제했다. 그러나 양자 이론의 선형성으로부터 임의의 상태 에 대해 삭제 연산을 수행할 수 있는 는 존재하지 않는다는 것이 따른다.
양자 상태 비소거 정리 정식 진술
시스템 에 대한 세 개의 힐베르트 공간이 주어지고, 시스템 에 대한 힐베르트 공간은 동일하다.
만약 가 유니터리 변환이고, 가 보조 상태이며, 다음을 만족한다면 여기서 보조 상태 의 최종 상태는 에 의존할 수 있으며, 이 경우 는 스와핑 연산인데, 이는  매핑이 등거리 임베딩이라는 의미이다.
이 정리는 임의의 차원의 힐베르트 공간에 있는 양자 상태에 대해 성립한다. 간단히 하기 위해, 두 개의 동일한 큐비트에 대한 삭제 변환을 고려해 보자. 만약 두 큐비트가 직교 상태에 있다면, 삭제는 다음을 요구한다.
,
.
를 알 수 없는 큐비트의 상태라고 하자. 만약 알 수 없는 큐비트의 두 복사본을 가지고 있다면, 삭제 변환의 선형성에 의해 다음을 얻는다.
위 표현에서 다음 변환이 사용되었다.
양자 상태 비소거 정리 정식 진술
그러나 만약 복사본을 삭제할 수 있다면, 삭제 기계의 출력 포트에서 결합된 상태는 다음과 같아야 한다.
.
일반적으로 이 상태들은 동일하지 않으므로 기계가 복사본을 삭제하는 데 실패했다고 말할 수 있다. 최종 출력 상태가 동일하도록 요구한다면, 단 하나의 선택만이 있음을 알 수 있다.
그리고
보조 상태 의 최종 상태는 의 모든 값에 대해 정규화되므로, 와 는 직교해야 한다. 이는 양자 정보가 단순히 보조 상태의 최종 상태에 있다는 것을 의미한다. 보조 힐베르트 공간에 대한 국소 연산을 사용하여 보조 상태의 최종 상태로부터 알 수 없는 상태를 항상 얻을 수 있다. 따라서 양자 이론의 선형성은 알 수 없는 양자 상태가 완벽하게 삭제되는 것을 허용하지 않는다.
그로버 알고리즘
양자 컴퓨팅에서 그로버 탐색 알고리즘은 양자 탐색 알고리즘으로도 알려져 있으며, 특정 출력값을 생성하는 블랙박스 함수의 고유 입력을 높은 확률로 찾는 비정형 탐색을 위한 양자 알고리즘이다. 이 함수는 함수의 정의역 크기를 이라고 할 때 번만 평가하면 된다. 이 알고리즘은 1996년 로브 그로버에 의해 고안되었다.
고전적 계산에서 유사한 문제는 의 쿼리 복잡도를 가지는데(즉, 함수를 번 평가해야 한다: 평균적으로  단계를 거쳐 모든 입력 값을 하나씩 시도하는 것보다 더 나은 접근 방식은 없다).
찰스 H. 베넷, 이선 번스타인, 질 브라사르, 그리고 우메시 바지라니는 문제에 대한 어떤 양자 해결책도 함수를 번 평가해야 함을 증명했으며, 따라서 그로버 탐색 알고리즘은 점근적으로 최적이다. NP-완전 문제에 대한 고전적 알고리즘은 지수적으로 많은 단계를 요구하며, 그로버 탐색 알고리즘은 비정형 탐색에 대한 고전적 해결책에 비해 기껏해야 제곱근 속도 향상을 제공하므로, 그로버 탐색 알고리즘 자체만으로는 NP-완전 문제에 대한 다항 시간 해결책을 제공하지 못함을 시사한다 (지수 함수의 제곱근은 여전히 다항 함수가 아닌 지수 함수이기 때문이다).
그로버 알고리즘
고전적 알고리즘에 비해 지수적 속도 향상을 제공할 수 있는 다른 양자 알고리즘과 달리, 그로버 탐색 알고리즘은 제곱근 속도 향상만을 제공한다. 그러나 이 클 때 제곱근 속도 향상조차도 상당하며, 그로버 탐색 알고리즘은 광범위한 알고리즘의 속도를 높이는 데 적용될 수 있다. 그로버 탐색 알고리즘은 128비트 대칭 암호화 키를 약 264회 반복으로, 256비트 키를 약 2128회 반복으로 무차별 대입할 수 있다. 그러나 그로버 탐색 알고리즘이 기존 고전적 알고리즘에 비해 암호화에 대한 위험을 크게 증가시키지는 않을 수 있다.
그로버 알고리즘 응용과 한계
그로버 탐색 알고리즘은 진폭 증폭과 같은 변형과 함께 광범위한 알고리즘의 속도를 높이는 데 사용될 수 있다. 특히, 완전 탐색을 서브루틴으로 포함하는 NP-완전 문제 알고리즘은 그로버 탐색 알고리즘에 의해 속도가 향상될 수 있다. 3SAT에 대한 최악의 경우 복잡도 측면에서 현재 이론적으로 가장 좋은 알고리즘이 그러한 예시이다. 일반적인 제약 충족 문제도 그로버 탐색 알고리즘으로 제곱근 속도 향상을 보인다. 이러한 알고리즘은 그로버 탐색 알고리즘이 명시적 함수(예: 비트 집합이 3SAT 인스턴스를 만족하는지 확인하는 함수)와 함께 적용되므로 입력이 오라클 형태로 주어질 필요가 없다. 그러나 그로버 탐색 알고리즘이 이러한 문제에 대한 최상의 실제 알고리즘의 속도를 높일 수 있는지는 불분명하다.
그로버 탐색 알고리즘은 양자 쿼리 복잡도에서 원소 구별성과 충돌 문제를 포함한 블랙박스 문제에 대해 증명 가능한 속도 향상을 제공할 수 있다 (브라사르-호이어-탭 알고리즘으로 해결). 이러한 유형의 문제에서 오라클 함수 f는 데이터베이스로 취급되며, 목표는 이 함수에 대한 양자 쿼리를 가능한 한 적게 사용하는 것이다.
그로버 알고리즘 응용과 한계
그로버 탐색 알고리즘은 본질적으로 함수 역산의 과제를 해결한다. 대략적으로 말하면, 양자 컴퓨터에서 평가될 수 있는 함수 가 있다면, 그로버 탐색 알고리즘은 가 주어졌을 때 를 계산할 수 있게 해준다. 결과적으로, 그로버 탐색 알고리즘은 충돌 공격 및 원상 공격을 포함한 대칭 키 암호에 대한 여러 종류의 무차별 대입 공격에 광범위한 점근적 속도 향상을 제공한다. 그러나 예를 들어, 폴라드 로 알고리즘은 그로버 탐색 알고리즘보다 SHA-2에서 충돌을 더 효율적으로 찾을 수 있으므로 이것이 반드시 가장 효율적인 알고리즘은 아닐 수 있다.
그로버 알고리즘 응용과 한계
그로버의 원래 논문은 이 알고리즘을 데이터베이스 탐색 알고리즘으로 설명했으며, 이 설명은 여전히 흔하다. 이 비유에서 데이터베이스는 해당 입력으로 인덱싱된 모든 함수의 출력 테이블이다. 그러나 이 데이터베이스는 명시적으로 표현되지 않는다. 대신, 오라클이 인덱스로 항목을 평가하기 위해 호출된다. 전체 데이터베이스 항목을 하나씩 읽고 그러한 표현으로 변환하는 것은 그로버 탐색보다 훨씬 오래 걸릴 수 있다. 이러한 효과를 설명하기 위해 그로버 알고리즘은 방정식을 풀거나 제약 조건을 만족시키는 것으로 볼 수 있다. 이러한 응용 프로그램에서 오라클은 제약 조건을 확인하는 방법이며 탐색 알고리즘과 관련이 없다. 이러한 분리는 일반적으로 알고리즘 최적화를 방지하는 반면, 기존 탐색 알고리즘은 종종 이러한 최적화에 의존하고 완전 탐색을 피한다. 다행히도, 많은 제약 충족 및 최적화 문제에 대해 빠른 그로버 오라클 구현이 가능하다.
그로버 알고리즘의 속도 향상을 구현하는 데 있어 주요 장벽은 달성된 2차 속도 향상이 근시일 내 양자 컴퓨터의 큰 오버헤드를 극복하기에는 너무 미미하다는 것이다. 그러나 더 나은 하드웨어 성능을 가진 차세대 오류 내성 양자 컴퓨터는 실제 데이터 인스턴스에 대해 이러한 속도 향상을 실현할 수 있을 것이다.
그로버 알고리즘 문제 설명
그로버 알고리즘의 입력으로, 함수 가 있다고 가정하자. "비정형 데이터베이스" 비유에서, 도메인은 데이터베이스에 대한 인덱스를 나타내며, f(x) = 1은 x가 가리키는 데이터가 검색 기준을 만족할 때에만 해당된다. 또한 우리는 오직 하나의 인덱스만이 f(x) = 1을 만족하며, 이 인덱스를 ω라고 부른다. 우리의 목표는 ω를 식별하는 것이다.
우리는 유니터리 작용소 Uω 형태로 서브루틴(때때로 오라클이라고 불림)을 사용하여 f에 접근할 수 있으며, Uω는 다음과 같이 작동한다:
이는  큐비트를 가진 양자 레지스터가 제공하는 -차원 상태 공간 를 사용한다.
이는 종종 다음과 같이 쓰여진다:
그로버 탐색 알고리즘은 Uω를 번 적용하여 최소 1/2의 확률로 ω를 출력한다. 이 확률은 그로버 탐색 알고리즘을 여러 번 실행함으로써 임의로 크게 만들 수 있다. ω가 발견될 때까지 그로버 탐색 알고리즘을 실행하면, 기대되는 적용 횟수는 평균적으로 두 번만 실행되므로 여전히 이다.
그로버 알고리즘 문제 설명
이 섹션에서는 위 오라클 를 오라클 와 비교한다.
Uω는 함수 f에 대한 표준 양자 오라클과 다르다. 이 표준 오라클은 여기서 Uf로 표기되며, 보조 큐비트 시스템을 사용한다. 연산은 보조 시스템의 f(x) 값에 따라 주 시스템에서 NOT 게이트 반전 연산을 나타낸다.
또는 간단히,
이러한 오라클은 일반적으로 역계산을 사용하여 구현된다.
만약 Uf가 오라클로 주어진다면, Uω도 구현할 수 있다. Uω는 보조 큐비트가 상태 에 있을 때 Uf와 같기 때문이다.
따라서 어떤 오라클이 주어지든 그로버 탐색 알고리즘은 실행될 수 있다. Uf가 주어지면, 우리는  상태에 있는 추가 큐비트를 유지하고 Uω 대신 Uf를 적용해야 한다.
그로버 알고리즘 알고리즘
그로버 탐색 알고리즘의 단계는 다음과 같다.
올바르게 선택된  값에 대해, N ≫ 1일 때 출력은 1에 가까운 확률로 가 된다. 분석 결과 의 최종 값은 을 만족한다.
이 알고리즘의 단계를 구현하는 것은 큐비트 수에 비례하는 게이트 수로 가능하다. 따라서 이 알고리즘의 게이트 복잡도는  또는 반복당 이다.
그로버 알고리즘 기하학적 증명
그로버 탐색 알고리즘은 각 단계 후 양자 상태가 2차원 부분 공간에 머무른다는 관찰에 따라 기하학적 해석을 갖는다. 와 에 의해 생성되는 평면을 고려하자. 동등하게, 와 수직 켓 에 의해 생성되는 평면을 고려하자.
그로버 탐색 알고리즘은 부분 공간에 놓인 초기 켓 로 시작한다. 연산자 는 와 에 의해 생성되는 평면의 벡터에 대해 에 수직인 초평면에서 반사이다. 즉, 에 대한 반사로 작동한다. 이는 를 하우스홀더 반사 형태로 작성함으로써 알 수 있다.
연산자 는 를 통한 반사이다. 두 연산자 와 는 와 에 의해 생성되는 평면의 상태를 평면의 상태로 변환한다. 따라서 그로버 탐색 알고리즘은 전체 알고리즘 동안 이 평면에 머무른다.
그로버 알고리즘 기하학적 증명
각 그로버 반복 단계의 연산자 가 상태 벡터를 만큼 회전시킨다는 것은 쉽게 확인할 수 있다. 따라서 충분한 반복을 통해 초기 상태 에서 원하는 출력 상태 로 회전할 수 있다. 초기 켓은 에 수직인 상태에 가깝다.
기하학적으로, 와  사이의 각도 는 다음과 같이 주어진다.
상태 벡터가 에 가까워졌을 때 멈춰야 한다. 그 후의 반복은 상태 벡터를 에서 멀어지게 하여 올바른 답을 얻을 확률을 감소시킨다. 올바른 답을 측정할 정확한 확률은 다음과 같다.
여기서 r은 그로버 반복 횟수(정수)이다. 따라서 거의 최적의 측정을 얻는 가장 빠른 시간은 이다.
그로버 알고리즘 대수적 증명
대수적 분석을 완성하기 위해 를 반복적으로 적용할 때 어떤 일이 발생하는지 알아야 한다. 이를 수행하는 자연스러운 방법은 행렬의 고유값 분석을 통하는 것이다. 전체 계산 동안 알고리즘의 상태는 와 의 선형 결합이라는 점에 주목하자. 로 생성되는 공간에서 와 의 작용을 다음과 같이 쓸 수 있다.
따라서  기저(이는 직교 기저도, 전체 공간의 기저도 아니다)에서  다음에 를 적용하는 의 작용은 다음 행렬로 주어진다.
이 행렬은 매우 편리한 조르당 표준형을 가지고 있다. 라고 정의하면,
여기서
따라서 r-번째 행렬 거듭제곱(r번 반복에 해당)은 다음과 같다.
이 형태를 사용하여 삼각 함수 항등식을 통해 이전 섹션에서 언급된 r번의 반복 후 ω를 관찰할 확률을 계산할 수 있다.
또는, 최적에 가까운 구별 시간이 2rt와 −2rt 각도가 가능한 한 멀리 떨어져 있을 때, 즉  또는 일 때라고 합리적으로 상상할 수 있다. 그러면 시스템은 다음 상태에 있게 된다.
간단한 계산을 통해 관찰 결과가 의 오차로 올바른 답인 ω를 산출함을 알 수 있다.
그로버 알고리즘 확장 및 변형
만약 일치하는 항목이 1개가 아니라 k개라면, 동일한 알고리즘이 작동하지만 반복 횟수는  대신 여야 한다.
k를 알 수 없는 경우를 처리하는 여러 가지 방법이 있다. 간단한 해결책은 상수 계수까지 최적으로 작동한다: k 값을 점진적으로 줄여가면서 그로버 탐색 알고리즘을 반복적으로 실행한다. 예를 들어, 일치하는 항목이 발견될 때까지 t번째 반복에서 와 같이 를 취한다.
충분히 높은 확률로, 일부 상수 c에 대해  반복으로 표시된 항목이 발견될 것이다. 따라서 총 반복 횟수는 최대
k를 알 수 없는 경우의 또 다른 접근 방식은 양자 계수 알고리즘을 통해 사전에 이를 도출하는 것이다.
만약  (또는 로 실행되는 기존의 단일 표시 상태 그로버 알고리즘)이라면, 알고리즘은 증폭을 제공하지 않을 것이다. 만약 라면, k가 증가함에 따라 해를 얻는 데 필요한 반복 횟수가 증가하기 시작할 것이다. 반면에, 만약 라면, 단일 무작위 입력 선택에 대한 고전적인 확인 오라클 실행은 정답을 줄 가능성이 더 높다.
그로버 알고리즘 확장 및 변형
이 알고리즘의 변형은 충돌 문제를 해결하는 데 사용된다.
그로버와 라다크리슈난은 2004년에 그로버 탐색 알고리즘의 변형인 양자 부분 탐색을 설명했다. 부분 탐색에서는 대상 항목의 정확한 주소를 찾는 것이 아니라 주소의 처음 몇 자리 숫자에만 관심이 있다. 동등하게, 검색 공간을 블록으로 "나누고" "대상 항목이 어느 블록에 있는가?"라고 묻는 것으로 생각할 수 있다. 많은 응용 분야에서, 대상 주소에 원하는 정보가 포함되어 있다면 이러한 검색만으로도 충분한 정보를 제공한다. 예를 들어, L. K. 그로버가 제시한 예시를 사용하면, 학급 석차별로 정리된 학생 목록이 있을 때, 학생이 하위 25%, 25–50%, 50–75% 또는 75–100% 백분위수에 속하는지에만 관심이 있을 수 있다.
그로버 알고리즘 확장 및 변형
부분 탐색을 설명하기 위해, 각각  크기의 개 블록으로 분리된 데이터베이스를 고려한다. 부분 탐색 문제는 더 쉽다. 고전적으로 우리가 취할 접근 방식을 고려해 보자 – 무작위로 하나의 블록을 선택한 다음 나머지 블록(집합론적 언어에서는 보완)을 통해 일반적인 검색을 수행한다. 대상을 찾지 못하면, 검색하지 않은 블록에 있다는 것을 알 수 있다. 평균 반복 횟수는 에서 로 줄어든다.
그로버 탐색 알고리즘은 번의 반복을 필요로 한다. 부분 탐색은 블록 수 에 따라 달라지는 수치적 요인만큼 더 빠를 것이다. 부분 탐색은 번의 전역 반복과 번의 지역 반복을 사용한다. 전역 그로버 연산자는 로, 지역 그로버 연산자는 로 지정된다.
글로벌 그로버 연산자는 블록에 작용한다. 기본적으로 다음과 같이 주어진다.
과 의 최적 값은 그로버와 라다크리슈난의 논문에서 논의된다. 또한, "해상도"의 다른 수준에서 연속적인 부분 탐색을 적용하면 어떻게 되는지 궁금할 수도 있다. 이 아이디어는 블라디미르 코레핀과 쉬에 의해 자세히 연구되었으며, 그들은 이를 이진 양자 탐색이라고 불렀다. 그들은 이것이 단일 부분 탐색을 수행하는 것보다 실제로 더 빠르지 않음을 증명했다.
그로버 알고리즘 최적성
그로버 탐색 알고리즘은 부상수 요인까지 최적이다. 즉, 연산자 Uω만을 사용하여 데이터베이스에 접근하는 어떤 알고리즘도 그로버 탐색 알고리즘만큼 최소  비율의 Uω를 적용해야 한다. k개의 일치하는 항목에 대한 그로버 탐색 알고리즘의 확장, π(N/k)1/2/4 또한 최적이다. 이 결과는 양자 계산의 한계를 이해하는 데 중요하다.
만약 그로버 탐색 문제가 Uω를 번 적용하여 해결될 수 있었다면, NP 문제를 그로버 유형 탐색 문제로 변환함으로써 NP가 BQP에 포함된다는 것을 의미할 것이다. 그로버 탐색 알고리즘의 최적성은 양자 컴퓨터가 NP-완전 문제를 다항 시간 내에 해결할 수 없으며, 따라서 NP가 BQP에 포함되지 않는다는 것을 시사한다.
비지역 숨은 변수 양자 컴퓨터의 한 종류는 개 항목 데이터베이스의 검색을 최대  단계 내에 구현할 수 있음이 밝혀졌다. 이는 그로버 탐색 알고리즘이 걸리는  단계보다 빠르다.
그로버 알고리즘 각주
Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today The Sciences, July/August 1999, pp. 24–30.
양자 담금질
양자 담금질 또는 양자 어닐링(Quantum annealing, QA)은 양자 요동을 이용한 과정을 통해 주어진 후보 해 집합(후보 상태)에서 주어진 목표 함수의 전역 최솟값을 찾는 최적화 과정이다. 양자 담금질은 탐색 공간이 조합 최적화 문제와 같이 많은 극소점을 가진 이산 공간이거나, 스핀 유리의 바닥 상태를 찾거나, 최대 절단, 그래프 색칠, 충족 가능성, 외판원 문제와 같은 다양한 문제를 인코딩할 수 있는 QUBO 문제를 해결하는 데 주로 사용된다. "양자 담금질"이라는 용어는 1988년 B. 아폴로니, N. 체사 비안키, D. 드 팔코가 양자 영감을 받은 고전 알고리즘으로 처음 제안했다. 1994년 A. B. 핀닐라, M. A. 고메스, C. 세베니크, J. D. 돌이 양자 결맞음이 없는 허수 시간 변형에 대해 논의했지만, 현재의 형태는 1998년 T. 가도와키와 H. 니시모리(ja)에 의해 정립되었다.
양자 담금질
양자 담금질은 모든 가능한 상태(후보 상태)의 양자역학적 중첩에서 동일한 가중치로 시작한다. 그런 다음 시스템은 물리적 시스템의 자연적인 양자역학적 진화인 시간에 따라 달라지는 슈뢰딩거 방정식을 따른다. 모든 후보 상태의 진폭은 시간에 따라 달라지는 횡단 필드의 강도에 따라 계속 변하여 양자 병렬 처리를 실현한다. 횡단 필드는 상태 간 또는 본질적으로 피크를 통한 양자 터널링을 유발한다. 횡단 필드의 변화율이 충분히 느리면 시스템은 순간 해밀토니언의 바닥 상태에 가깝게 유지된다(또한 단열 양자 계산 참조). 횡단 필드의 변화율이 가속되면 시스템은 일시적으로 바닥 상태를 벗어날 수 있지만 최종 문제 해밀토니언의 바닥 상태에 도달할 가능성이 더 높아진다. 즉, 비단열 양자 계산이다. 횡단 필드는 마침내 꺼지고, 시스템은 원래 최적화 문제의 해에 해당하는 고전 이징 모형의 바닥 상태에 도달할 것으로 예상된다. 무작위 자석에 대한 양자 담금질 성공의 실험적 시연은 초기 이론적 제안 직후 보고되었다. 양자 담금질은 많은 NP-완전 문제 해결에서 제곱근 속도 향상을 위한 빠른 그로버 오라클을 제공하는 것으로도 입증되었다.
양자 담금질 담금질 기법과의 비교
양자 담금질은 양자 담금질의 터널링 필드 강도와 유사한 역할을 하는 "온도" 매개변수를 가진 담금질 기법과 비교할 수 있다. 담금질 기법에서 온도는 단일 현재 상태에서 더 높은 "에너지" 상태로 이동할 확률을 결정한다. 양자 담금질에서 횡단 필드의 강도는 모든 상태의 진폭을 병렬로 변경할 양자역학적 확률을 결정한다. 분석적 및 수치적 증거는 특정 조건에서 양자 담금질이 담금질 기법보다 우수함을 시사한다(하이엠 등과 양자 담금질의 임의 대상 해밀토니언에 대한 완전히 해결 가능한 모형 및 다양한 계산 방식의 비교를 위한 옌과 시니친 참조).
양자 담금질 양자 역학: 유추와 장점
터널링 필드는 기본적으로 원래 유리의 고전적 퍼텐셜 에너지 부분과 교환하지 않는 운동 에너지 항이다. 전체 과정은 양자 몬테카를로(또는 다른 확률적 기술)를 사용하여 컴퓨터에서 시뮬레이션될 수 있으므로 고전적 유리의 바닥 상태를 찾는 휴리스틱 알고리즘을 얻을 수 있다.
순수하게 수학적인 목적 함수를 담금질하는 경우, 문제의 변수를 고전적인 자유도로 간주하고 비용 함수를 퍼텐셜 에너지 함수(고전 해밀토니언)로 간주할 수 있다. 그런 다음 원래 수학적 문제의 변수와 0이 아닌 교환자를 갖는 변수(즉, 교환하지 않는 변수)로 구성된 적절한 항을 해밀토니언에 인위적으로 도입하여 터널링 필드(운동 부분)의 역할을 수행해야 한다. 그런 다음 위에서 설명한 대로 구성된 양자 해밀토니니언(원래 함수 + 비교환 부분)으로 시뮬레이션을 수행할 수 있다. 여기서 비비교환 항을 선택하는 데 선택의 여지가 있으며 담금질의 효율성은 이에 따라 달라질 수 있다.
양자 담금질 양자 역학: 유추와 장점
양자 담금질은 특정 경우, 특히 퍼텐셜 에너지(비용) 지형이 얕은 지역 최솟값을 둘러싸는 매우 높지만 얇은 장벽으로 구성된 경우에 열 담금질(담금질 기법)보다 우수하다는 것이 실험적으로나 이론적으로 입증되었다. 열 전이 확률(는 온도, 는 볼츠만 상수인 에 비례)은 장벽의 높이 에만 의존하기 때문에 매우 높은 장벽의 경우 열 요동이 시스템을 그러한 지역 최솟값에서 벗어나게 하는 것은 극히 어렵다. 그러나 1989년 레이, 차크라바티, 차크라바티가 일찍이 주장했듯이, 동일한 장벽을 통한 양자 터널링 확률(단독으로 고려됨)은 장벽의 높이 뿐만 아니라 너비 에도 의존하며 대략 로 주어진다. 여기서 는 터널링 필드이다. 양자 터널링이 있는 경우 너비 를 통한 이 추가 제어는 큰 도움이 될 수 있다. 장벽이 충분히 얇으면(즉, ), 양자 요동은 시스템을 얕은 지역 최솟값에서 확실히 벗어나게 할 수 있다. -스핀 유리에서 장벽 높이 는  정도가 된다. 가 상수 값인 경우 담금질 시간은 에 비례하고(열 담금질의 경우 에 비례하는  대신), 가 로 감소하는 경우에는 가 에 무관하게 될 수도 있다.
양자 담금질 양자 역학: 유추와 장점
양자 컴퓨터에서 이러한 시뮬레이션은 고전 컴퓨터에서 수행되는 것보다 훨씬 효율적이고 정확할 것으로 예상되는데, 이는 터널링을 수동으로 추가할 필요 없이 직접 수행할 수 있기 때문이다. 더욱이, 더 전통적인 양자 알고리즘에 사용되는 양자 얽힘을 활용하는 데 필요한 엄격한 오류 제어 없이도 이를 수행할 수 있을 것이다. 이에 대한 일부 확인은 정확히 해결 가능한 모델에서 발견된다.
이징 스핀 유리에서 양자 담금질과 관련된 아이디어의 타임라인:
양자 담금질 D-웨이브 구현
2011년, D-웨이브 시스템은 D-Wave One이라는 이름으로 시장에 첫 상용 양자 담금질기를 발표하고 그 성능에 대한 논문을 네이처에 게재했다. 이 회사는 이 시스템이 128 큐비트 프로세서 칩셋을 사용한다고 주장한다. 2011년 5월 25일, D-Wave는 록히드 마틴 기업이 D-Wave One 시스템을 구매하는 계약을 체결했다고 발표했다. 2011년 10월 28일 서던캘리포니아 대학교 (USC)의 정보과학연구소는 록히드 마틴의 D-Wave One을 인도받았다.
2013년 5월, 구글, NASA 에임스 및 비영리 우주연구 대학연합 컨소시엄이 512큐비트의 D-Wave 시스템으로부터 단열 양자 컴퓨터를 구매했다고 발표되었다. 일부 고전 담금질 알고리즘과 비교하여 양자 담금질기로서의 성능에 대한 광범위한 연구가 가능하다.
양자 담금질 D-웨이브 구현
2014년 6월, D-Wave는 계산 금융 회사인 1QB 인포메이션 테크놀로지스(1QBit) 및 암 연구 그룹인 DNA-SEQ와 함께 양자 하드웨어를 사용하여 실제 문제를 해결하는 데 중점을 둘 새로운 양자 애플리케이션 생태계를 발표했다. 상업적으로 이용 가능한 양자 컴퓨터용 소프트웨어 응용 프로그램을 생산하는 데 전념하는 최초의 회사로서 1QBit의 연구 개발 부서는 D-Wave의 양자 담금질 프로세서에 중점을 두었으며 이러한 프로세서가 실제 응용 프로그램을 해결하는 데 적합함을 입증했다.